Premium
A generalization of an edge‐connectivity theorem of Chartrand
Author(s) -
Boesch Frank,
Gross Daniel,
Saccoman John T.,
Kazmierczak L. William,
Suffel Charles,
Suhartomo Antonius
Publication year - 2009
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20297
Subject(s) - mathematics , degree (music) , combinatorics , connectivity , generalization , graph , enhanced data rates for gsm evolution , vertex connectivity , order (exchange) , discrete mathematics , computer science , artificial intelligence , mathematical analysis , physics , finance , acoustics , vertex (graph theory) , economics
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 . Results are established that guarantee that this parameter is at least as large as the minimum degree, provided the minimum degree is sufficiently large. This generalizes Chartrand's result. It is also determined when these results are best possible. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009