Czechoslovak Mathematical Journal, Vol. 71, No. 4, pp. 1071-1098, 2021
Fiedler vectors with unbalanced sign patterns
Sooyeong Kim, Steve Kirkland
Received May 14, 2020. Published online April 16, 2021.
Abstract: 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.