| Title:
|
Fiedler vectors with unbalanced sign patterns (English) |
| Author:
|
Kim, Sooyeong |
| Author:
|
Kirkland, Steve |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
71 |
| Issue:
|
4 |
| Year:
|
2021 |
| Pages:
|
1071-1098 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
In spectral bisection, a Fielder vector is used for partitioning a graph into two connected subgraphs according to its sign pattern. We investigate graphs having Fiedler vectors with unbalanced sign patterns such that a partition can result in two connected subgraphs that are distinctly different in size. We present a characterization of graphs having a Fiedler vector with exactly one negative component, and discuss some classes of such graphs. We also establish an analogous result for regular graphs with a Fiedler vector with exactly two negative components. In particular, we examine the circumstances under which any Fiedler vector has unbalanced sign pattern according to the number of vertices with minimum degree. (English) |
| Keyword:
|
algebraic connectivity |
| Keyword:
|
Fiedler vector |
| Keyword:
|
minimum degree |
| MSC:
|
05C50 |
| MSC:
|
15A18 |
| idZBL:
|
Zbl 07442475 |
| idMR:
|
MR4339112 |
| DOI:
|
10.21136/CMJ.2021.0198-20 |
| . |
| Date available:
|
2021-11-08T16:01:23Z |
| Last updated:
|
2024-01-01 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/149239 |
| . |
| Reference:
|
[1] Brouwer, A. E., Haemers, W. H.: Spectra of Graphs.Universitext. Springer, New York (2012). Zbl 1231.05001, MR 2882891, 10.1007/978-1-4614-1939-6 |
| Reference:
|
[2] Cvetković, D., Rowlinson, P., Simić, S.: Spectral Generalizations of Line Graphs: On Graphs with Least Eigenvalue $-2$.London Mathematical Society Lecture Note Series 314. Cambridge University Press, Cambridge (2004). Zbl 1061.05057, MR 2120511, 10.1017/CBO9780511751752 |
| Reference:
|
[3] Cvetković, D., Simić, S.: The second largest eigenvalue of a graph (a survey).Filomat 9 (1995), 449-472. Zbl 0851.05078, MR 1385931 |
| Reference:
|
[4] Fiedler, M.: Algebraic connectivity of graphs.Czech. Math. J. 23 (1973), 298-305. Zbl 0265.05119, MR 0318007, 10.21136/CMJ.1973.101168 |
| 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, 10.21136/CMJ.1975.101357 |
| Reference:
|
[6] Kirkland, S. J., Molitierno, J. J., Neumann, M., Shader, B. L.: On graphs with equal algebraic and vertex connectivity.Linear Algebra Appl. 341 (2002), 45-56. Zbl 0991.05071, MR 1873608, 10.1016/S0024-3795(01)00312-3 |
| Reference:
|
[7] Merris, R.: Degree maximal graphs are Laplacian integral.Linear Algebra Appl. 199 (1994), 381-389. Zbl 0795.05091, MR 1274427, 10.1016/0024-3795(94)90361-1 |
| Reference:
|
[8] Merris, R.: Laplacian graph eigenvectors.Linear Algebra Appl. 278 (1998), 221-236. Zbl 0932.05057, MR 1637359, 10.1016/S0024-3795(97)10080-5 |
| Reference:
|
[9] Seidel, J. J.: Strongly regular graphs with $(-1,1,0)$ adjacency matrix having eigenvalue 3.Linear Algebra Appl. 1 (1968), 281-298. Zbl 0159.25403, MR 234861, 10.1016/0024-3795(68)90008-6 |
| Reference:
|
[10] Urschel, J. C., Zikatanov, L. T.: Spectral bisection of graphs and connectedness.Linear Algebra Appl. 449 (2014), 1-16. Zbl 1286.05101, MR 3191855, 10.1016/j.laa.2014.02.007 |
| Reference:
|
[11] Urschel, J. C., Zikatanov, L. T.: On the maximal error of spectral approximation of graph bisection.Linear Multilinear Algebra 64 (2016), 1972-1979. Zbl 1352.05120, MR 3521152, 10.1080/03081087.2015.1133557 |
| . |
