✦ LIBER ✦

2-factors in triangle-free graphs

✍ Scribed by Bauer, D.; van den Heuvel, J.; Schmeichel, E.

Publisher: John Wiley and Sons
Year: 1996
Tongue: English
Weight: 440 KB
Volume: 21
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199604)21:4<405::aid-jgt6>3.0.co;2-t

No coin nor oath required. For personal study only.

✦ Synopsis

We study the cycle structure of I-tough, triangle-free graphs. In particular, w e prove that every such graph on n 2 3 vertices with minimum degree 6 2 i ( n + 2) has a 2-factor. W e also show this is best possible by exhibiting an infinite class of I-tough, triangle-free graphs having 6 = $ ( n + 1) and no 2-factor. 0

📜 SIMILAR VOLUMES

On triangle-free random graphs

✍ Tomasz Łuczak 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 167 KB 👁 1 views

We show that for every k ≥ 1 and δ > 0 there exists a constant c > 0 such that, with probability tending to 1 as n → ∞, a graph chosen uniformly at random among all triangle-free graphs with n vertices and M ≥ cn 3/2 edges can be made bipartite by deleting δM edges. As an immediate consequence of th

Triangles in 2-factorizations

✍ Dejter, I. J.; Franek, F.; Mendelsohn, E.; Rosa, A. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 128 KB 👁 1 views

The triangle-spectrum for 2-factorizations of the complete graph K v is the set of all numbers δ such that there exists a 2-factorization of K v in which the total number of triangles equals δ. By applying mainly design-theoretic methods, we determine the triangle spectrum for all v ≡ 1 or 3 (mod 6)

Closure, 2-factors, and cycle coverings

Closure, 2-factors, and cycle coverings in claw-free graphs

✍ Ryj�?ek, Zden?k; Saito, Akira; Schelp, R. H. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 239 KB 👁 2 views

In this article, we study cycle coverings and 2-factors of a claw-free graph and those of its closure, which has been defined by the first author (On a closure concept in claw-free graphs, J Combin Theory Ser B 70 (1997), 217-224). For a claw-free graph G and its closure cl(G), we prove: ( 1 (2) G

2-factors in random regular graphs

✍ Robalewska, Hanna D. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 474 KB 👁 1 views

In this paper the expectation and variance of the number of 2-factors in random r-regular graphs for any fixed r 2 3 is analyzed and the asymptotic distribution of this variable is determined.

On decomposition of triangle-free graphs

On decomposition of triangle-free graphs under degree constraints

✍ Kaneko, Atsushi 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 80 KB 👁 1 views

We prove that if s and t are positive integers and if G is a triangle-free graph with minimum degree s + t, then the vertex set of G has a decomposition into two sets which induce subgraphs of minimum degree at least s and t, respectively.

Triangle-free graphs that are signable w

Triangle-free graphs that are signable without even holes

✍ Michele Conforti; Gérard Cornuéjols; Ajai Kapoor; Kristina Vušković 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 172 KB 👁 1 views