Seminár z algebratickej teórie grafov - Róbert Jajcay (1.12.2017)

v piatok 1.12.2017 o 13:30 hod. v miestnosti M/XI

29. 11. 2017 12.39 hod.
Od: Martin Mačaj

Prednášajúca: Róbert Jajcay

Názov: On the non-existence of digraphs whose order is close to the Moore bound and which contain only self-repeat vertices

Termín: 1.12.2017, 13:30 hod., M/XI (akvárium)

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.