Algebraic Graph Theory Seminar - Tom Raiman (5.4.2019)

Friday 5.4.2019 at 13:30, Lecture room IX

---

Tom Raiman (VSB-TU Ostrava):
Recursive methods for determining spectra of (k; g)-graphs

Abstract:
A (k,g)-graph is k-regular graph with girth g. We present conditions under which we can add vertices to (k,g)-graphs. This is the opposite approach to common techniques, where we are searching for smallest pos- sible (k,g)-graph. With these conditions we may create innite series of (k,g)-graphs (with repetitive use of our conditions), we call the series of ascending orders a spectra of (k,g)-graph. The aim of our approach is to obtain inside under what conditions we can obtain spectra of (k,g)- graphs for any pair k,g. In case of (3,g)-graphs we were able to obtain new bound for existence of spectra of (3,g)-graphs. Our bound is better than classical and long-standing bound obtained by Sauer. If the order of (3,g)-graph lies between our bound and bound of Sauer, than we can construct the whole spectra of (3,g)-graphs, for given g. We will also discuss newly obtained spectra for some k's of (k,6)- and (k,8)-graphs.

 

 

---