✦ LIBER ✦

Supereulerian graphs, independent sets, and degree-sum conditions

✍ Scribed by Zhi-Hong Chen

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 573 KB
Volume: 179
Category: Article
ISSN: 0012-365X
DOI: 10.1016/s0012-365x(97)00028-9

No coin nor oath required. For personal study only.

✦ Synopsis

A graph is supereulerian if it contains a spanning closed trail. A graph G is collapsible if for every even subset R C V(G), there is a spanning connected subgraph of G whose set of odd degree vertices is R. The graph K1 is regarded as a trivial collapsible graph. A graph is reduced if it contains no nontrivial collapsible subgraphs. In this paper, we study the independence numbers of reduced graphs. As an application, we also obtain new degree-sum conditions for supereulerian graphs and collapsible graphs. Let R = {u, v} if u ~ v, and let R = 0 if u = v. Then, IRI is even. By the definition of a collapsible graph, G has a spanning connected subgraph HR such that O(HR) = R.

📜 SIMILAR VOLUMES

Degree multiplicities and independent se

Degree multiplicities and independent sets in K4-free graphs

✍ Béla Bollobás 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 555 KB

Neighborhood conditions for balanced ind

Neighborhood conditions for balanced independent sets in bipartite graphs

✍ Denise Amar; Stephan Brandt; Daniel Brito; Oscar Ordaz 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 319 KB

Let G be a balanced bipartite graph of order 2n and minimum degree 6(G)>~3. If, for every balanced independent set S of four vertices, IN(S)I >n then G is traceable, the circumference is at least 2n -2 and G contains a 2-factor (with only small order exceptional graphs for the latter statement). If

Generalized degree conditions for graphs

Generalized degree conditions for graphs with bounded independence number

✍ Ralph Faudree; Ronald J. Gould; Linda Lesniak; Terri Lindquester 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 511 KB

We consider a generalized degree condition based on the cardinality of the neighborhood union of arbitrary sets of r vertices. We show that a Dirac-type bound on this degree in conjunction with a bound on the independence number of a graph is sufficient to imply certain hamiltonian properties in gra

Independent sets and repeated degrees

✍ B. Bollobás; A.D. Scott 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 316 KB

Bipartite Graphs and their Degree Sets

✍ Y. Manoussakis; H.P. Patil 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 69 KB

Schedules on graphs and independent sets

Schedules on graphs and independent sets of graphs

✍ A. I. Kuksa 📂 Article 📅 1973 🏛 Springer US 🌐 English ⚖ 338 KB