| Title:
|
Algebraic connectivity of $k$-connected graphs (English) |
| Author:
|
Kirkland, Steve |
| Author:
|
Rocha, Israel |
| Author:
|
Trevisan, Vilmar |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
65 |
| Issue:
|
1 |
| Year:
|
2015 |
| Pages:
|
219-236 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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). (English) |
| Keyword:
|
algebraic connectivity |
| Keyword:
|
Fiedler vector |
| MSC:
|
05C50 |
| MSC:
|
15A18 |
| idZBL:
|
Zbl 06433731 |
| idMR:
|
MR3336035 |
| DOI:
|
10.1007/s10587-015-0170-9 |
| . |
| Date available:
|
2015-04-01T12:36:45Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/144223 |
| . |
| Reference:
|
[1] Bapat, R. B., Kirkland, S. J., Pati, S.: The perturbed Laplacian matrix of a graph.Linear Multilinear Algebra 49 (2001), 219-242. Zbl 0984.05056, MR 1888190, 10.1080/03081080108818697 |
| Reference:
|
[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. Zbl 1244.05139, MR 2903493, 10.1080/03081087.2011.603727 |
| Reference:
|
[3] Bapat, R. B., Pati, S.: Algebraic connectivity and the characteristic set of a graph.Linear Multilinear Algebra 45 (1998), 247-273. Zbl 0944.05066, MR 1671627, 10.1080/03081089808818590 |
| Reference:
|
[4] Abreu, N. M. M. de: Old and new results on algebraic connectivity of graphs.Linear Algebra Appl. 423 (2007), 53-73. Zbl 1115.05056, MR 2312323, 10.1016/j.laa.2006.08.017 |
| Reference:
|
[5] Fiedler, M.: A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory.Czech. Math. J. 25 (1975), 619-633. Zbl 0437.15004, MR 0387321 |
| Reference:
|
[6] Fiedler, M.: Algebraic connectivity of graphs.Czech. Math. J. 23 (1973), 298-305. Zbl 0265.05119, MR 0318007 |
| Reference:
|
[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 3013937 |
| Reference:
|
[8] Kirkland, S., Neumann, M., Shader, B. L.: Characteristic vertices of weighted trees via Perron values.Linear Multilinear Algebra 40 (1996), 311-325. Zbl 0866.05041, MR 1384650, 10.1080/03081089608818448 |
| Reference:
|
[9] Kirkland, S., Fallat, S.: Perron components and algebraic connectivity for weighted graphs.Linear Multilinear Algebra 44 (1998), 131-148. Zbl 0926.05026, MR 1674228, 10.1080/03081089808818554 |
| Reference:
|
[10] Merris, R.: Laplacian matrices of graphs: a survey.Linear Algebra Appl. 197-198 (1994), 143-176. Zbl 0802.05053, MR 1275613 |
| Reference:
|
[11] Nikiforov, V.: The influence of Miroslav Fiedler on spectral graph theory.Linear Algebra Appl. 439 (2013), 818-821. Zbl 1282.05145, MR 3061737 |
| Reference:
|
[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. Zbl 0711.65034, MR 1054210, 10.1137/0611030 |
| . |
