Fakulta matematiky, fyziky
a informatiky
Univerzita Komenského v Bratislave

Seminár z algebraickej teórie grafov - Tom Raiman (5.4.2019)

v piatok 5.4.2019 o 13:30 hod., v miestnosti M/IX


03. 04. 2019 08.36 hod.
Od: Martin Mačaj

Prednášajúci: Tom Raiman (VSB-TU Ostrava) 

Názov:  Recursive methods for determining spectra of (k; g)-graphs

Termín: 5.4.2019, 13:30 hod., M/IX


Abstrakt:
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.