A Generalization of an Edge-Connectivity Theorem of Chartrand
Journal Networks, 52(2), 82- 89, September 2009
Daniel Gross, Ph.D. Department of Mathematics and Computer Science
John T Saccoman, Jr. Ph.D.Department of Mathematics and Computer Science
F. Boesch, L. Kazmierczak, C. Suffel & A. Suhartomo
In 1966, Chartrand proved that if the minimum degree of a graph is at least the floor of half the number of nodes, then its edge-connectivity equals its minimum degree. A more discriminating notion of edge-connectivity is introduced, called the k-component order edge-connectivity, which is the minimum number of edges required to be removed so that the order of each component of the resulting subgraph is less than k.