Preskoči na glavno vsebino

Bojan Mohar: Is there a structural graph theory based on the spectral radius?

Datum objave: 14. 4. 2009
Seminar za teorijo grafov in algoritme
Četrtek 16. 4. 2009 ob 12:15 v predavalnici 3.07 na Jadranski 21.
Every tree of maximum degree $D$ is a subgraph of the infinite $D$-regular tree. This observation immediately implies that the spectral radius of every such tree is at most $2\sqrt{D-1}$. One can also show (T. Hayes, V. Nikiforov, Z. Dvo\v rak and B. Mohar) that planar graphs and graphs of bounded genus satisfy a similar relation: the spectral radius is $O(D^{1/2})$. Whenever a result can be proved for tree-like graphs and for graphs of bounded genus, it is natural to ask if it can be extended to a more general setting of minor-closed families (or beyond) and what new tools does it bring. In the talk we will try to answer this question.