Geodesic
Algebraic connectivity of $k$-connected graphs
Czechoslovak Mathematical Journal, Tome 65 (2015) no. 1, pp. 219-236 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

Let $G$ be a $k$-connected graph with $k \ge 2$. A hinge is a subset of $k$ vertices whose deletion from $G$ yields a disconnected graph. We consider the algebraic connectivity and Fiedler vectors of such graphs, paying special attention to the signs of the entries in Fiedler vectors corresponding to vertices in a hinge, and to vertices in the connected components at a hinge. The results extend those in Fiedler's papers Algebraic connectivity of graphs (1973), A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory (1975), and Kirkland and Fallat's paper Perron Components and Algebraic Connectivity for Weighted Graphs (1998).
Let $G$ be a $k$-connected graph with $k \ge 2$. A hinge is a subset of $k$ vertices whose deletion from $G$ yields a disconnected graph. We consider the algebraic connectivity and Fiedler vectors of such graphs, paying special attention to the signs of the entries in Fiedler vectors corresponding to vertices in a hinge, and to vertices in the connected components at a hinge. The results extend those in Fiedler's papers Algebraic connectivity of graphs (1973), A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory (1975), and Kirkland and Fallat's paper Perron Components and Algebraic Connectivity for Weighted Graphs (1998).
DOI : 10.1007/s10587-015-0170-9
Classification : 05C50, 15A18
Keywords: algebraic connectivity; Fiedler vector 
@article{10_1007_s10587_015_0170_9,
     author = {Kirkland, Steve and Rocha, Israel and Trevisan, Vilmar},
     title = {Algebraic connectivity of $k$-connected graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {219--236},
     year = {2015},
     volume = {65},
     number = {1},
     doi = {10.1007/s10587-015-0170-9},
     mrnumber = {3336035},
     zbl = {06433731},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1007/s10587-015-0170-9/}
}
TY  - JOUR
AU  - Kirkland, Steve
AU  - Rocha, Israel
AU  - Trevisan, Vilmar
TI  - Algebraic connectivity of $k$-connected graphs
JO  - Czechoslovak Mathematical Journal
PY  - 2015
SP  - 219
EP  - 236
VL  - 65
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.1007/s10587-015-0170-9/
DO  - 10.1007/s10587-015-0170-9
LA  - en
ID  - 10_1007_s10587_015_0170_9
ER  - 
%0 Journal Article
%A Kirkland, Steve
%A Rocha, Israel
%A Trevisan, Vilmar
%T Algebraic connectivity of $k$-connected graphs
%J Czechoslovak Mathematical Journal
%D 2015
%P 219-236
%V 65
%N 1
%U http://geodesic.mathdoc.fr/articles/10.1007/s10587-015-0170-9/
%R 10.1007/s10587-015-0170-9
%G en
%F 10_1007_s10587_015_0170_9
Kirkland, Steve; Rocha, Israel; Trevisan, Vilmar. Algebraic connectivity of $k$-connected graphs. Czechoslovak Mathematical Journal, Tome 65 (2015) no. 1, pp. 219-236. doi: 10.1007/s10587-015-0170-9

[1] Bapat, R. B., Kirkland, S. J., Pati, S.: The perturbed Laplacian matrix of a graph. Linear Multilinear Algebra 49 (2001), 219-242. | DOI | MR | Zbl

[2] Bapat, R. B., Lal, A. K., Pati, S.: On algebraic connectivity of graphs with at most two points of articulation in each block. Linear Multilinear Algebra 60 (2012), 415-432. | DOI | MR | Zbl

[3] Bapat, R. B., Pati, S.: Algebraic connectivity and the characteristic set of a graph. Linear Multilinear Algebra 45 (1998), 247-273. | DOI | MR | Zbl

[4] Abreu, N. M. M. de: Old and new results on algebraic connectivity of graphs. Linear Algebra Appl. 423 (2007), 53-73. | DOI | MR | Zbl

[5] Fiedler, M.: A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory. Czech. Math. J. 25 (1975), 619-633. | MR | Zbl

[6] Fiedler, M.: Algebraic connectivity of graphs. Czech. Math. J. 23 (1973), 298-305. | MR | Zbl

[7] Kirkland, S.: Algebraic connectivity. Handbook of Linear Algebra Discrete Mathematics and Its Applications Chapman & Hall/CRC, Boca Raton (2007), 36-1-36-12 L. Hogben et al. | MR

[8] Kirkland, S., Neumann, M., Shader, B. L.: Characteristic vertices of weighted trees via Perron values. Linear Multilinear Algebra 40 (1996), 311-325. | DOI | MR | Zbl

[9] Kirkland, S., Fallat, S.: Perron components and algebraic connectivity for weighted graphs. Linear Multilinear Algebra 44 (1998), 131-148. | DOI | MR | Zbl

[10] Merris, R.: Laplacian matrices of graphs: a survey. Linear Algebra Appl. 197-198 (1994), 143-176. | MR | Zbl

[11] Nikiforov, V.: The influence of Miroslav Fiedler on spectral graph theory. Linear Algebra Appl. 439 (2013), 818-821. | MR | Zbl

[12] Pothen, A., Simon, H. D., Liou, K.-P.: Partitioning sparse matrices with eigenvectors of graphs. SIAM J. Matrix Anal. Appl. 11 (1990), 430-452. | DOI | MR | Zbl

Cité par Sources :