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

Cité par Sources :