On the Fiedler value of large planar graphs

被引：8

作者：

Barriere, Lali ^{[1
]}

Huemer, Clemens ^{[1
]}

Mitsche, Dieter ^{[1
]}

Orden, David ^{[2
]}

机构：

[1] Univ Politecn Cataluna, Dept Matemat Aplicada 4, E-08028 Barcelona, Spain

[2] Univ Alcala, Dept Fis & Matemat, Alcala De Henares, Spain

来源：

LINEAR ALGEBRA AND ITS APPLICATIONS | 2013年 / 439卷 / 07期

基金：

加拿大自然科学与工程研究理事会;

关键词：

Fiedler value; Algebraic connectivity; Laplacian matrix; Planar graph; Bounded genus graph; Minor-free graph; ALGEBRAIC CONNECTIVITY; EXTREMAL FUNCTION; EIGENVALUES;

D O I：

10.1016/j.laa.2013.05.032

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The Fiedler value lambda(2), also known as algebraic connectivity, is the second smallest Laplacian eigenvalue of a graph. We study the maximum Fiedler value among all planar graphs G with n vertices, denoted by lambda(2max), and we show the bounds 2 + Theta(1/n2) <= lambda(2max) <= 2 + O(1/n). We also provide bounds on the maximum Fiedler value for the following classes of planar graphs: Bipartite planar graphs, bipartite planar graphs with minimum vertex-degree 3, and outerplanar graphs. Furthermore, we derive almost tight bounds on lambda(2max) for two more classes of graphs, those of bounded genus and K-h-minor-free graphs. (C) 2013 Elsevier Inc. All rights reserved.

引用

页码：2070 / 2084

页数：15

共 22 条

[1]

ALON N, 1990, J AM MATH SOC, V3, P801

[2]

Barriere L., 2011, ELECT NOTES DISCRETE, V38, P111, DOI DOI 10.1016/J.ENDM.2011.09.019

[3] Eigenvalue Bounds, Spectral Partitioning, and Metrical Deformations via Flows [J].

Biswal, Punyashloka ;

Lee, James R. ;

Rao, Satish .

JOURNAL OF THE ACM, 2010, 57 (03)

[4]

Brouwer AE, 2012, UNIVERSITEXT, P1, DOI 10.1007/978-1-4614-1939-6

[5] Old and new results on algebraic connectivity of graphs [J].

de Abreu, Nair Maria Maia .

LINEAR ALGEBRA AND ITS APPLICATIONS, 2007, 423 (01) :53-73

[6]

Elsner U., 1997, SFB3939727 TU CHEMN

[7]

FIEDLER M, 1973, CZECH MATH J, V23, P298

[8]

Freitas P., 2001, A heawood-type result for the algebraic connectivity of graphs on surfaces

[9] A SEPARATOR THEOREM FOR GRAPHS OF BOUNDED GENUS [J].

GILBERT, JR ;

HUTCHINSON, JP ;

TARJAN, RE .

JOURNAL OF ALGORITHMS, 1984, 5 (03) :391-407

[10] A separator theorem in minor-closed classes [J].

Kawarabayashi, Ken-ichi ;

Reed, Bruce .

2010 IEEE 51ST ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, 2010, :153-162

← 1 2 3 →