✦ LIBER ✦

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

✍ Scribed by Rao Li; Akira Saito; R.H. Schelp

Publisher: John Wiley and Sons
Year: 2001
Tongue: English
Weight: 184 KB
Volume: 37
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.1009

No coin nor oath required. For personal study only.

✦ Synopsis

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}$ for every independent set {x~1~, x~2~, x~3~, x~4~}, then G satisfies c(G) ≥ p(G) − 1. Using this result, we give several lower bounds to the circumference of a 3‐connected graph. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 137–156, 2001

📜 SIMILAR VOLUMES

On relative length of longest paths and

On relative length of longest paths and cycles

✍ Kenta Ozeki; Masao Tsugaki; Tomoki Yamashita 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 144 KB 👁 1 views

## Abstract For a graph __G__, __p__(__G__) and __c__(__G__) denote the order of a longest path and a longest cycle of __G__, respectively. In this paper, we prove that if __G__ is a 3 ‐connected graph of order __n__ such that the minimum degree sum of four independent vertices is at least __n__+ 6

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

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 👁 1 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.

Longest cycles in 3-connected graphs con

Longest cycles in 3-connected graphs contain three contractible edges

✍ Nathaniel Dean; Robert L. Hemminger; Katsuhiro Ota 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 221 KB 👁 1 views

We show that if G is a 3-connected graph of order at least seven, then every longest path between distinct vertices in G contains at least two contractible edges. An immediate corollary is that longest cycles in such graphs contain at least three contractible edges. We consider only finite undirect

Toughness and longest cycles in 2-connec

Toughness and longest cycles in 2-connected planar graphs

✍ B�hme, T.; Broersma, H. J.; Veldman, H. J. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 390 KB 👁 2 views

Let G be a planar graph on n vertices, let c(G) denote the length of a longest cycle of G, and let w(G) denote the number of components of G. By a well-known theorem of Tutte, c(G) = n (i.e., G is hamiltonian) if G is 4-connected. Recently, Jackson and Wormald showed that c(G) 2 ona for some positiv

A degree sum condition for longest cycle

A degree sum condition for longest cycles in 3-connected graphs

✍ Tomoki Yamashita 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 110 KB 👁 1 views

## Abstract For a graph __G__, we denote by __d__~__G__~(__x__) and κ(__G__) the degree of a vertex __x__ in __G__ and the connectivity of __G__, respectively. In this article, we show that if __G__ is a 3‐connected graph of order __n__ such that __d__~__G__~(__x__) + __d__~__G__~(__y__) + __d__~__