Geodesic
Fiedler vectors with unbalanced sign patterns
Czechoslovak Mathematical Journal, Tome 71 (2021) no. 4, pp. 1071-1098
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.21136/CMJ.2021.0198-20
Classification : 05C50, 15A18
Keywords: algebraic connectivity; Fiedler vector; minimum degree 
@article{10_21136_CMJ_2021_0198_20,
     author = {Kim, Sooyeong and Kirkland, Steve},
     title = {Fiedler vectors with unbalanced sign patterns},
     journal = {Czechoslovak Mathematical Journal},
     pages = {1071--1098},
     year = {2021},
     volume = {71},
     number = {4},
     doi = {10.21136/CMJ.2021.0198-20},
     mrnumber = {4339112},
     zbl = {07442475},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2021.0198-20/}
}
TY  - JOUR
AU  - Kim, Sooyeong
AU  - Kirkland, Steve
TI  - Fiedler vectors with unbalanced sign patterns
JO  - Czechoslovak Mathematical Journal
PY  - 2021
SP  - 1071
EP  - 1098
VL  - 71
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2021.0198-20/
DO  - 10.21136/CMJ.2021.0198-20
LA  - en
ID  - 10_21136_CMJ_2021_0198_20
ER  - 
%0 Journal Article
%A Kim, Sooyeong
%A Kirkland, Steve
%T Fiedler vectors with unbalanced sign patterns
%J Czechoslovak Mathematical Journal
%D 2021
%P 1071-1098
%V 71
%N 4
%U http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2021.0198-20/
%R 10.21136/CMJ.2021.0198-20
%G en
%F 10_21136_CMJ_2021_0198_20
Kim, Sooyeong; Kirkland, Steve. Fiedler vectors with unbalanced sign patterns. Czechoslovak Mathematical Journal, Tome 71 (2021) no. 4, pp. 1071-1098. doi: 10.21136/CMJ.2021.0198-20

[1] Brouwer, A. E., Haemers, W. H.: Spectra of Graphs. Universitext. Springer, New York (2012). | DOI | MR | JFM

[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 | MR | JFM

[3] Cvetković, D., Simić, S.: The second largest eigenvalue of a graph (a survey). Filomat 9 (1995), 449-472. | MR | JFM

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

[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 | MR | JFM

[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 | MR | JFM

[7] Merris, R.: Degree maximal graphs are Laplacian integral. Linear Algebra Appl. 199 (1994), 381-389. | DOI | MR | JFM

[8] Merris, R.: Laplacian graph eigenvectors. Linear Algebra Appl. 278 (1998), 221-236. | DOI | MR | JFM

[9] Seidel, J. J.: Strongly regular graphs with $(-1,1,0)$ adjacency matrix having eigenvalue 3. Linear Algebra Appl. 1 (1968), 281-298. | DOI | MR | JFM

[10] Urschel, J. C., Zikatanov, L. T.: Spectral bisection of graphs and connectedness. Linear Algebra Appl. 449 (2014), 1-16. | DOI | MR | JFM

[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 | MR | JFM

Cité par Sources :