The Spectral Radius of Graphs on Surfaces
The Spectral Radius of Graphs on Surfaces
复制标题
DOI：
10.1006/jctb.1999.1926
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
M. Ellingham;X. Zha
中科院分区：
文献类型：
--
作者：
M. Ellingham;X. Zha
给出了谱半径？的新上界。(邻接矩阵的最大特征值)可嵌入到给定紧致曲面上的图。我们的方法是利用欧拉公式的简单推论，确定邻接矩阵的一个多项式的最大行和的界。让？表示固定曲面的欧拉亏格(横帽数加句柄数的两倍)？那么(I)对于n？3，每个n-点图都可嵌入？有2+2n+8？6，以及(Ii)球面或4-代表嵌入到？上的4-连通图。3.结果(I)是不尖锐的，正如Guiduli和Hayes最近证明了？对于嵌入在固定曲面上的图，3/2+2n+o(1)是否为n？∞？然而，(I)是唯一可计算的、对所有n？3有效并且与2n渐近的、类似于？的实际最大值的界。结果(Ii)对于球面或平面(？=0)是尖锐的，当且仅当图是一个“双轮”2K1+Cn？2(+表示联图)时等式成立。对于其他曲面，我们证明了(Ii)在O(1/n1/2)的锐度范围内。我们还表明，近期反弹了吗？可以用我们的方法推导出。
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 ?. Then (i) for n?3, every n-vertex graph embeddable on ? has ??2+2n+8??6, and (ii) a 4-connected graph with a spherical or 4-representative embedding on ? 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” 2K1+Cn?2 (+denotes join). For other surfaces we show that (ii) is within O(1/n1/2) of sharpness. We also show that a recent bound on ? by Hong can be deduced by our method.