Article
Full entry |
PDF
(0.4 MB)
Feedback
PDF
(0.4 MB)
Feedback
Keywords:
algebraic connectivity; Fiedler vector; minimum degree
algebraic connectivity; Fiedler vector; minimum degree
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.
References:
[1] Brouwer, A. E., Haemers, W. H.: Spectra of Graphs. Universitext. Springer, New York (2012). DOI 10.1007/978-1-4614-1939-6 | MR 2882891 | Zbl 1231.05001
[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). DOI 10.1017/CBO9780511751752 | MR 2120511 | Zbl 1061.05057
[3] Cvetković, D., Simić, S.: The second largest eigenvalue of a graph (a survey). Filomat 9 (1995), 449-472. MR 1385931 | Zbl 0851.05078
[4] Fiedler, M.: Algebraic connectivity of graphs. Czech. Math. J. 23 (1973), 298-305. DOI 10.21136/CMJ.1973.101168 | MR 0318007 | Zbl 0265.05119
[5] Fiedler, M.: A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory. Czech. Math. J. 25 (1975), 619-633. DOI 10.21136/CMJ.1975.101357 | MR 0387321 | Zbl 0437.15004
[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. DOI 10.1016/S0024-3795(01)00312-3 | MR 1873608 | Zbl 0991.05071
[7] Merris, R.: Degree maximal graphs are Laplacian integral. Linear Algebra Appl. 199 (1994), 381-389. DOI 10.1016/0024-3795(94)90361-1 | MR 1274427 | Zbl 0795.05091
[8] Merris, R.: Laplacian graph eigenvectors. Linear Algebra Appl. 278 (1998), 221-236. DOI 10.1016/S0024-3795(97)10080-5 | MR 1637359 | Zbl 0932.05057
[9] Seidel, J. J.: Strongly regular graphs with $(-1,1,0)$ adjacency matrix having eigenvalue 3. Linear Algebra Appl. 1 (1968), 281-298. DOI 10.1016/0024-3795(68)90008-6 | MR 234861 | Zbl 0159.25403
[10] Urschel, J. C., Zikatanov, L. T.: Spectral bisection of graphs and connectedness. Linear Algebra Appl. 449 (2014), 1-16. DOI 10.1016/j.laa.2014.02.007 | MR 3191855 | Zbl 1286.05101
[11] Urschel, J. C., Zikatanov, L. T.: On the maximal error of spectral approximation of graph bisection. Linear Multilinear Algebra 64 (2016), 1972-1979. DOI 10.1080/03081087.2015.1133557 | MR 3521152 | Zbl 1352.05120
Search
Partner of
