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