TY - JOUR

T1 - Spectral bisection of graphs and connectedness

AU - Urschel, John C.

AU - Zikatanov, Ludmil T.

N1 - Funding Information:
The research of Ludmil Zikatanov was supported in part by NSF grant DMS-1217142 , and Lawrence Livermore National Laboratory through subcontract B603526 .

PY - 2014/5/15

Y1 - 2014/5/15

N2 - We present a refinement of the work of Miroslav Fiedler regarding bisections of irreducible matrices. We consider graph bisections as defined by the cut set consisting of characteristic edges of the eigenvector corresponding to the smallest non-zero eigenvalue of the graph Laplacian (the so-called Fiedler vector). We provide a simple and transparent analysis, including the cases when there exist components with value zero. Namely, we extend the class of graphs for which the Fiedler vector is guaranteed to produce connected subgraphs in the bisection. Furthermore, we show that for all connected graphs there exist Fiedler vectors such that connectedness is preserved by the bisection, and estimate the measure of the set of connectedness preserving Fiedler vectors with respect to the set of all Fiedler vectors.

AB - We present a refinement of the work of Miroslav Fiedler regarding bisections of irreducible matrices. We consider graph bisections as defined by the cut set consisting of characteristic edges of the eigenvector corresponding to the smallest non-zero eigenvalue of the graph Laplacian (the so-called Fiedler vector). We provide a simple and transparent analysis, including the cases when there exist components with value zero. Namely, we extend the class of graphs for which the Fiedler vector is guaranteed to produce connected subgraphs in the bisection. Furthermore, we show that for all connected graphs there exist Fiedler vectors such that connectedness is preserved by the bisection, and estimate the measure of the set of connectedness preserving Fiedler vectors with respect to the set of all Fiedler vectors.

UR - http://www.scopus.com/inward/record.url?scp=84894807155&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84894807155&partnerID=8YFLogxK

U2 - 10.1016/j.laa.2014.02.007

DO - 10.1016/j.laa.2014.02.007

M3 - Article

AN - SCOPUS:84894807155

SN - 0024-3795

VL - 449

SP - 1

EP - 16

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

ER -