Spectral radius of finite and infinite planar graphs and of graphs of bounded genus

Details Spectral radius of finite and infinite planar graphs and of graphs of bounded genus Spectral radius of finite and infinite planar graphs and of graphs of bounded genus

2009-07-09

arxiv.org/abs/0907.1591v1

J. Combin. Theory Ser. B 100 (2010) 729-739

Mathematics

Combinatorics

Scientific paper

10.1016/j.jctb.2010.07.006

It is well known that the spectral radius of a tree whose maximum degree is $D$ cannot exceed $2\sqrt{D-1}$. In this paper we derive similar bounds for arbitrary planar graphs and for graphs of bounded genus. It is proved that a the spectral radius $\rho(G)$ of a planar graph $G$ of maximum vertex degree $D\ge 4$ satisfies $\sqrt{D}\le \rho(G)\le \sqrt{8D-16}+7.75$. This result is best possible up to the additive constant--we construct an (infinite) planar graph of maximum degree $D$, whose spectral radius is $\sqrt{8D-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.

Affiliated with

Also associated with

No associations

Rating

Spectral radius of finite and infinite planar graphs and of graphs of bounded genus does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Spectral radius of finite and infinite planar graphs and of graphs of bounded genus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Spectral radius of finite and infinite planar graphs and of graphs of bounded genus will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-341988