A Heawood-type result for the algebraic connectivity of graphs on surfaces

Details A Heawood-type result for the algebraic connectivity of graphs on surfaces A Heawood-type result for the algebraic connectivity of graphs on surfaces

2001-09-24

arxiv.org/abs/math/0109191v1

Mathematics

Combinatorics

13 pages

Scientific paper

We prove that the algebraic connectivity a(G) of a graph embedded on a nonplanar surface satisfies a Heawood-type result. More precisely, it is shown that the algebraic connectivity of a surface S, defined as the supremum of a(G) over all graphs that can be embedded in S, is equal to the chromatic number of S. Furthermore, and with the possible exception of the Klein bottle, we prove that this bound is attained only in the case of the maximal complete graph that can be embedded in S. In the planar case, we show that, at least for some classes of graphs which include the set of regular graphs, a(G) is less than or equal to four. As an application of these results and techniques, we obtain a lower bound for the genus of Ramanujan graphs. We also present some bounds for the asymptotic behaviour of a(G) for certain classes of graphs as the number of vertices goes to infinity.

Affiliated with

Also associated with

No associations

Rating

A Heawood-type result for the algebraic connectivity of graphs on surfaces 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 A Heawood-type result for the algebraic connectivity of graphs on surfaces, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Heawood-type result for the algebraic connectivity of graphs on surfaces will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-308170