✦ LIBER ✦

Longest paths and cycles in K1,3-free graphs

✍ Scribed by Manton M. Matthews; David P. Sumner

Publisher: John Wiley and Sons
Year: 1985
Tongue: English
Weight: 383 KB
Volume: 9
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190090208

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

Longest paths and cycles in bipartite or

Longest paths and cycles in bipartite oriented graphs

✍ Zhang Ke Min 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 430 KB 👁 1 views

In this paper we obtain two sufficient conditions, Ore type (Theorem 1) and Dirac type (Theorem 2). on the degrees of a bipartite oriented graph for ensuring the existence of long paths and cycles. These conditions are shown to be the best possible in a sense. An oriented graph is a digraph without

Relative length of longest paths and cyc

Relative length of longest paths and cycles in 3-connected graphs

✍ Rao Li; Akira Saito; R.H. Schelp 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 184 KB 👁 2 views

## Abstract For a graph __G__, let __p(G)__ denote the order of a longest path in __G__ and __c(G)__ the order of a longest cycle in __G__, respectively. We show that if __G__ is a 3‐connected graph of order __n__ such that $\textstyle{\sum^{4}\_{i=1}\,{\rm deg}\_{G}\,x\_{i} \ge {3\over2}\,n + 1}$

On weights of induced paths and cycles i

On weights of induced paths and cycles in claw-free and K1,r-free graphs

✍ J. Harant; M. Voigt; S. Jendrol; B. Randerath; Z. Ryjáček; I. Schiermeyer 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 175 KB 👁 3 views

Longest cycles in tough graphs

✍ Jung, H.A.; Wittmann, P. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 347 KB 👁 2 views

In this article, we establish bounds for the length of a longest cycle C in a 2-connected graph G in terms of the minimum degree δ and the toughness t. It is shown that C is a Hamiltonian cycle or |C| ≥ (t + 1)δ + t.

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.

Hamiltonian results in K1,3-free graphs

✍ M. M. Matthews; D. P. Sumner 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 357 KB 👁 1 views

There have been a number of results dealing with Hamiltonian properties in powers of graphs. In this paper we show that the square and the total graph of a K,,,-free graph are vertex pancyclic. We then discuss some of the relationships between connectivity and Hamiltonian properties in K,.3-free gra