𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A generalization of an edge-connectivity theorem of Chartrand

✍ Scribed by Frank Boesch; Daniel Gross; John T. Saccoman; L. William Kazmierczak; Charles Suffel; Antonius Suhartomo

Publisher
John Wiley and Sons
Year
2009
Tongue
English
Weight
134 KB
Volume
54
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

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

📜 SIMILAR VOLUMES

A Generalization of an Addition Theorem
A Generalization of an Addition Theorem of Kneser
✍ Xiang-Dong Hou; Ka Hin Leung; Qing Xiang 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 109 KB

A theorem of Kneser states that in an abelian group G; if A and B are finite subsets in G and AB ¼ fab : a 2 A; b 2 Bg; then jABj5jAj þ jBj À jHðABÞj where HðABÞ ¼ fg 2 G : gðABÞ ¼ ABg: Motivated by the study of a problem in finite fields, we prove an analogous result for vector spaces over a field

A generalization of Turán's theorem
A generalization of Turán's theorem
✍ Benny Sudakov; Tibor Szabó; H. Van Vu 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 94 KB

## Abstract In this paper, we obtain an asymptotic generalization of Turán's theorem. We prove that if all the non‐trivial eigenvalues of a __d__‐regular graph __G__ on __n__ vertices are sufficiently small, then the largest __K__~__t__~‐free subgraph of __G__ contains approximately (__t__ − 2)/(__

A Generalization of a Theorem of Dirac
A Generalization of a Theorem of Dirac
✍ Tristan Denley; Haidong Wu 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 85 KB

In this paper, we give a generalization of a well-known result of Dirac that given any k vertices in a k-connected graph where k 2, there is a circuit containing all of them. We also generalize a result of Ha ggkvist and Thomassen. Our main result partially answers an open matroid question of Oxley.

On a generalization of Rubin's theorem
On a generalization of Rubin's theorem
✍ Dmitry A. Shabanov 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 89 KB

The work is devoted to the calculation of asymptotic value of the choice number of the complete r-partite graph K m \* r = K m,. ..,m with equal part size m. We obtained the asymptotics in the case ln r = o(ln m). The proof generalizes the classical result of A.L. Rubin for the case r = 2.