On the algebraic connectivity of graphs as a function of genus

✍ Scribed by Jason J. Molitierno

• Publisher: Elsevier Science
• Year: 2006
• Tongue: English
• Weight: 295 KB
• Volume: 419
• Category: Article
• ISSN: 0024-3795
• DOI: 10.1016/j.laa.2006.05.014

✦ Synopsis

We find an upper bound on the algebraic connectivity of graphs of various genus. We begin by showing that for fixed k 1, the graph of genus k of largest algebraic connectivity is a complete graph. We then find an upper bound for noncomplete graphs of a fixed genus k 1 and we determine the values of k for which the upper bound can be attained. Finally, we find the upper bound of the algebraic connectivity of planar graphs (graphs of genus zero) and determine precisely which graphs attain this upper bound.