The Spectral Radius of Graphs on Surfaces

✍ Scribed by M.N. Ellingham; Xiaoya Zha

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 152 KB
• Volume: 78
• Category: Article
• ISSN: 0095-8956
• DOI: 10.1006/jctb.1999.1926

✦ Synopsis

This paper provides new upper bounds on the spectral radius \ (largest eigenvalue of the adjacency matrix) of graphs embeddable on a given compact surface. Our method is to bound the maximum rowsum in a polynomial of the adjacency matrix, using simple consequences of Euler's formula. Let # denote the Euler genus (the number of crosscaps plus twice the number of handles) of a fixed surface 7. Then (i) for n 3, every n-vertex graph embeddable on 7 has \ 2+-2n+8#&6, and (ii) a 4-connected graph with a spherical or 4-representative embedding on 7 has \ 1+-2n+2#&3. Result (i) is not sharp, as Guiduli and Hayes have recently proved that the maximum value of \ is 3Â2+-2n+o(1) as n Ä for graphs embeddable on a fixed surface. However, (i) is the only known bound that is computable, valid for all n 3, and asymptotic to -2n like the actual maximum value of . Result (ii) is sharp for the sphere or plane (#=0), with equality holding if and only if the graph is a ``double wheel'' 2K 1 +C n&2 (+ denotes join). For other surfaces we show that (ii) is within O(1Ân 1Â2 ) of sharpness. We also show that a recent bound on \ by Hong can be deduced by our method. 2000 Academic Press 1. INTRODUCTION Let G be an n-vertex graph with adjacency matrix A. In this paper graph means a simple graph, with no loops or multiple edges. The spectral radius \ of G is the largest eigenvalue of A. Schwenk and Wilson [11] suggested the study of the eigenvalues of planar graphs. At about the same time, the spectral radius of planar graphs