✦ LIBER ✦

Degree bounds for the circumference of 3-connected graphs

✍ Scribed by Heinz A. Jung; Elkin Vumar

Publisher: John Wiley and Sons
Year: 2005
Tongue: English
Weight: 229 KB
Volume: 50
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20092

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Let C be a longest cycle in the 3‐connected graph G and let H be a component of G − V(C) such that |V(H)| ≥ 3. We supply estimates of the form |C| ≥ 2__d__(u) + 2__d__(v) − α(4 ≤ α ≤ 8), where u,v are suitably chosen non‐adjacent vertices in G. Also the exceptional classes for α = 6,7,8 are characterized. © 2005 Wiley Periodicals, Inc. J Graph Theory

📜 SIMILAR VOLUMES

A degree condition for the circumference

A degree condition for the circumference of a graph

✍ Nathaniel Dean; Pierre Fraisse 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 198 KB 👁 1 views

We present a new condition on the degree sums of a graph that implies the existence of a long cycle. Let c(G) denote the length of a longest cycle in the graph G and let rn be any positive integer. Suppose G is a 2-connected graph with vertices x,, . . . , x, and edge set E that satisfies the proper

A sharp lower bound for the circumferenc

A sharp lower bound for the circumference of 1-tough graphs with large degree sums

✍ Vu Dinh Hoa 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 207 KB 👁 1 views

## Abstract We show that every 1‐tough graph __G__ on __n__ ≥ 3 vertices with σ~3~≧ __n__ has a cycle of length at least min{__n, n__ + (σ~3~/3 ) − α + 1}, where σ~3~ denotes the minimum value of the degree sum of any 3 pairwise nonadjacent vertices and α the cardinality of a miximum independent se

On the Circumferences of Regular 2-Conne

On the Circumferences of Regular 2-Connected Graphs

✍ Bing Wei 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 135 KB

Let G be a 2-connected d-regular graph on n rd (r 3) vertices and c(G) denote the circumference of G. Bondy conjectured that c(G) 2nÂ(r&1) if n is large enough. In this paper, we show that c(G) 2nÂ(r&1)+2(r&3)Â(r&1) for any integer r 3. In particular, G is hamiltonian if r=3. This generalizes a resu

Convex Programming and Circumference of

Convex Programming and Circumference of 3-Connected Graphs of Low Genus

✍ Zhicheng Gao; Xingxing Yu 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 376 KB

Long Cycles and 3-Connected Spanning Sub

Long Cycles and 3-Connected Spanning Subgraphs of Bounded Degree in 3-Connected K1, d-Free Graphs

✍ B. Jackson; N.C. Wormald 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 238 KB

Let \(G\) be a 3-connected \(K_{1, d}\)-free graph on \(n\) vertices. We show that \(G\) contains a 3-connected spanning subgraph of maximum degree at most \(2 d-1\). Using an earlier result of ours, we deduce that \(G\) contains a cycle of length at least \(\frac{1}{2} n^{c}\) where \(c=\left(\log

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__~__