期刊
JOURNAL OF COMBINATORIAL THEORY SERIES B
卷 100, 期 6, 页码 729-739出版社
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.jctb.2010.07.006
关键词
Spectral radius; Planar graph; Bounded genus
类别
资金
- Simon Fraser University
- NSERC (Canada)
- ARRS (Slovenia) [P1-0297]
It is well known that the spectral radius of a tree whose maximum degree is Delta cannot exceed 2 root Delta - 1. In this paper we derive similar bounds for arbitrary planar graphs and for graphs of bounded genus. Using the decomposition result of Goncalves (2009)191, we prove that the spectral radius p(G) of a planar graph G of maximum vertex degree Delta >= 2 satisfies p(G) <= root 8 Delta - 16 + 3.47. This result is best possible up to the additive constant we construct an (infinite) planar graph of maximum degree A, whose spectral radius is root 8 Delta - 16. This generalizes and improves several previous results and solves an open problem proposed by Tom Hayes. Similar bounds are derived for graphs of bounded genus. For every k, these bounds can be improved by excluding K-2.k as a subgraph. In particular, the upper bound is strengthened for 5-connected graphs. All our results hold for finite as well as for infinite graphs. At the end we enhance the graph decomposition method introduced in the first part of the paper and apply it to tessellations of the hyperbolic plane. We derive bounds on the spectral radius that are close to the true value, and even in the simplest case of regular tessellations of type (p, q) we derive an essential improvement over known results, obtaining exact estimates in the first-order term and non-trivial estimates for the second-order asymptotics. (C) 2010 Elsevier Inc. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据