Faculty of Mathematics, Physics
and InformaticsComenius University Bratislava
Main menu
Faculty of Mathematics, Physics and Informatics >

Algebraic Graph Theory Seminar - Róbert Jajcay (1.12.2017)

Friday 1.12.2017 at 13:30, Lecture room M/XI

29. 11. 2017 12.52 hod.
By: Martin Mačaj

Róbert Jajcay:
On the non-existence of digraphs whose order is close to the Moore bound and which contain only self-repeat verticesium)


Abstract:
We consider d-diregular digraphs (both the in-degree and the out-degree are equal to d) of diameter k. A vertex is a self-repeat if it is the only vertex in the graph which connects to it via two distinct paths of length not exceeding k. Many interesting graphs consist of self-repeats only. Using spectral methods, we show that no such graphs of order close to the Moore bound exist.