✦ LIBER ✦

Cycles of given length in some K1,3-free graphs

✍ Scribed by Cun-Quan Zhang

Publisher: Elsevier Science
Year: 1989
Tongue: English
Weight: 478 KB
Volume: 78
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(89)90186-6

No coin nor oath required. For personal study only.

✦ Synopsis

Let G be a non-trivial connected &,-free graph. If any vertex cut of G contains a veitex v such that G@!(u)) is connected, we prove that G is pancyclic. If G(Z+I(u)) is conaected for any vertex u of G, we prove that G is vertex pancyclic and obtain a polynomial time algorithm for constructing cycles of given length and passing through a given vertex in G.

📜 SIMILAR VOLUMES

Longest paths and cycles in K1,3-free gr

Longest paths and cycles in K1,3-free graphs

✍ Manton M. Matthews; David P. Sumner 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 383 KB 👁 2 views

In this article w e show that the standard results concerning longest paths and cycles in graphs can be improved for K,,,-free graphs. We obtain as a consequence of these results conditions for the existence of a hamiltonian path and cycle in K,,,-free graphs.

Cycles of length 0 modulo k in directed

Cycles of length 0 modulo k in directed graphs

✍ Noga Alon; N Linial 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 417 KB

Cycles of length 2 modulo 3 in graphs

✍ Akira Saito 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 274 KB

Saito, A., Cycles of length 2 modulo 3 in graphs, Discrete Mathematics 101 (1992) 285-289. We prove that if a graph G of minimum degree at least 3 has no cycle of length 2 (mod 3), then G has an induced subgraph which is isomorphic to either K4 or Ks,s. The above result together with its relatively

Cycles of even length in graphs

✍ J.A Bondy; M Simonovits 📂 Article 📅 1974 🏛 Elsevier Science 🌐 English ⚖ 363 KB

Relative lengths of paths and cycles in

Relative lengths of paths and cycles in k-connected graphs

✍ S.C Locke 📂 Article 📅 1982 🏛 Elsevier Science 🌐 English ⚖ 583 KB

Regular factors in K1,3-free graphs

✍ S. A. Choudum; M. S. Paulraj 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 247 KB 👁 1 views

## Abstract We show that every connected __K__~1,3~‐free graph with minimum degree at least __2k__ contains a __k__‐factor and construct connected __K__~1,3~‐free graphs with minimum degree __k__ + __0__(√__k__) that have no __k__‐factor.