Fiedler vectors with unbalanced sign patterns

Sooyeong Kim; Stephen J. Kirkland

Czechoslovak Mathematical Journal (2021)

  • Volume: 71, Issue: 4, page 1071-1098
  • ISSN: 0011-4642

Abstract

top
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.

How to cite

top

Kim, Sooyeong, and Kirkland, Stephen J.. "Fiedler vectors with unbalanced sign patterns." Czechoslovak Mathematical Journal 71.4 (2021): 1071-1098. <http://eudml.org/doc/298291>.

@article{Kim2021,
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.},
author = {Kim, Sooyeong, Kirkland, Stephen J.},
journal = {Czechoslovak Mathematical Journal},
keywords = {algebraic connectivity; Fiedler vector; minimum degree},
language = {eng},
number = {4},
pages = {1071-1098},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Fiedler vectors with unbalanced sign patterns},
url = {http://eudml.org/doc/298291},
volume = {71},
year = {2021},
}

TY - JOUR
AU - Kim, Sooyeong
AU - Kirkland, Stephen J.
TI - Fiedler vectors with unbalanced sign patterns
JO - Czechoslovak Mathematical Journal
PY - 2021
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 71
IS - 4
SP - 1071
EP - 1098
AB - 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.
LA - eng
KW - algebraic connectivity; Fiedler vector; minimum degree
UR - http://eudml.org/doc/298291
ER -

References

top
  1. Brouwer, A. E., Haemers, W. H., 10.1007/978-1-4614-1939-6, Universitext. Springer, New York (2012). (2012) Zbl1231.05001MR2882891DOI10.1007/978-1-4614-1939-6
  2. Cvetković, D., Rowlinson, P., Simić, S., 10.1017/CBO9780511751752, London Mathematical Society Lecture Note Series 314. Cambridge University Press, Cambridge (2004). (2004) Zbl1061.05057MR2120511DOI10.1017/CBO9780511751752
  3. Cvetković, D., Simić, S., The second largest eigenvalue of a graph (a survey), Filomat 9 (1995), 449-472. (1995) Zbl0851.05078MR1385931
  4. Fiedler, M., 10.21136/CMJ.1973.101168, Czech. Math. J. 23 (1973), 298-305. (1973) Zbl0265.05119MR0318007DOI10.21136/CMJ.1973.101168
  5. Fiedler, M., 10.21136/CMJ.1975.101357, Czech. Math. J. 25 (1975), 619-633. (1975) Zbl0437.15004MR0387321DOI10.21136/CMJ.1975.101357
  6. Kirkland, S. J., Molitierno, J. J., Neumann, M., Shader, B. L., 10.1016/S0024-3795(01)00312-3, Linear Algebra Appl. 341 (2002), 45-56. (2002) Zbl0991.05071MR1873608DOI10.1016/S0024-3795(01)00312-3
  7. Merris, R., 10.1016/0024-3795(94)90361-1, Linear Algebra Appl. 199 (1994), 381-389. (1994) Zbl0795.05091MR1274427DOI10.1016/0024-3795(94)90361-1
  8. Merris, R., 10.1016/S0024-3795(97)10080-5, Linear Algebra Appl. 278 (1998), 221-236. (1998) Zbl0932.05057MR1637359DOI10.1016/S0024-3795(97)10080-5
  9. Seidel, J. J., 10.1016/0024-3795(68)90008-6, Linear Algebra Appl. 1 (1968), 281-298. (1968) Zbl0159.25403MR234861DOI10.1016/0024-3795(68)90008-6
  10. Urschel, J. C., Zikatanov, L. T., 10.1016/j.laa.2014.02.007, Linear Algebra Appl. 449 (2014), 1-16. (2014) Zbl1286.05101MR3191855DOI10.1016/j.laa.2014.02.007
  11. Urschel, J. C., Zikatanov, L. T., 10.1080/03081087.2015.1133557, Linear Multilinear Algebra 64 (2016), 1972-1979. (2016) Zbl1352.05120MR3521152DOI10.1080/03081087.2015.1133557

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.