Structural properties of the minimum cut of partially-supplied graphs. Academic Article uri icon

abstract

  • It is well known that information about the structure of a graph is contained within its minimum cut. Here we investigate how the minimum cut of one graph informs the structure of a second, related graph. We consider pairs of graphs G and H, with respective Laplacian matrices L and M, and call H partially supplied provided M is a Schur complement of L. Our results show how the minimum cut of H relates to the structure of the larger graph G.

published proceedings

  • Discrete Appl Math

author list (cited authors)

  • Griffing, A. R., Lynch, B. R., & Stone, E. A.

citation count

  • 2

complete list of authors

  • Griffing, Alexander R||Lynch, Benjamin R||Stone, Eric A

publication date

  • January 2014