97-77: Some Results Concerning the Ends of Minimal Cuts of Simple Graphs

DIMACS TR: 97-77

Some Results Concerning the Ends of Minimal Cuts of Simple Graphs

Authors: Ning Jia and Xiaofeng Jia

ABSTRACT
Let S be a cut of a simple connected graph G.If S has no proper subset that is a cut, we say S is a minimal cut of G. To a minimal cut S, a connected component of G-S is called a fragment. And a fragment with no proper subset that is also a fragment is called an end. We characterized ends in our discussions and proved that to a connected graph G=(V,E), the number of its ends<=|V(G)|.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-77.ps.gz

DIMACS Home Page