The spectral radius of graphs on surfaces

This payer provides new upper bounds on the spectral radius rho (largest-eigen value 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 gamma denote the Euler genus (the number of crosscaps plus twice the number of handles) of a fixed surface Sigma. Then (i) for n greater than or equal to 3, every n-vertex graph embeddable on Sigma has rho less than or equal to 2 + root 2n + 8y - 6, and (ii) a 4-connected graph with a spherical or 3-representative embedding on Sigma has rho less than or equal to 1 + root 2n + 2y - 3. Result (i) is not sharp, as Guiduli and Hayes have recently proved that the maximum value of rho is 3/2 + root 2n + oil) as n --> rx? for graphs embeddable on a fixed surface, However. (i) is the only known bound that is computable, valid for all it greater than or equal to 3, and asymptotic to root 2n like the actual maximum value of rho. Result (ii) is sharp for the sphere or plane (gamma = 0), with equality holding if and only if the graph is a "double: wheel" 2K(1) + Cn-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 rho by Hong can be deduced by our method. (C) 2000 Academic Press.