Structural properties of the minimum cut of partially-supplied graphs

Alexander R. Griffing, Benjamin R. Lynch, Eric A. Stone*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)

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

Original languageEnglish
Pages (from-to)152-157
Number of pages6
JournalDiscrete Applied Mathematics
Volume177
DOIs
Publication statusPublished - 20 Nov 2014
Externally publishedYes

Fingerprint

Dive into the research topics of 'Structural properties of the minimum cut of partially-supplied graphs'. Together they form a unique fingerprint.

Cite this