✦ LIBER ✦

Relative length of long paths and cycles in graphs with large degree sums

✍ Scribed by Hikoe Enomoto; Jan van den Heuvel; Atsushi Kaneko; Akira Saito

Publisher: John Wiley and Sons
Year: 1995
Tongue: English
Weight: 601 KB
Volume: 20
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190200210

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

For a graph G, p(G) denotes the order of a longest path in G and c(G) the order of a longest cycle. We show that if G is a connected graph n ≥ 3 vertices such that d(u) + d(v) + d(w) ≧ n for all triples u, v, w of independent vertices, then G satisfies c(G) ≥ p(G) – 1, or G is in one of six families of exceptional graphs. This generalizes results of Bondy and of Bauer, Morgana, Schmeichel, and Veldman. © 1995, John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

Long cycles in graphs with large degree

Long cycles in graphs with large degree sums

✍ Douglas Bauer; H.J. Veldman; A. Morgana; E.F. Schmeichel 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 764 KB

Long cycles in graphs with large degree

Long cycles in graphs with large degree sums and neighborhood unions

✍ Van den Heuvel, J. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 801 KB

We present and prove several results concerning the length of longest cycles in 2connected or I-tough graphs with large degree sums. These results improve many known results on long cycles in these graphs. We also consider the sharpness of the results and discuss some possible strengthenings.

Cycles and paths in graphs with large mi

Cycles and paths in graphs with large minimal degree

✍ V. Nikiforov; R. H. Schelp 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 114 KB 👁 1 views

## Abstract Let __G__ be a simple graph of order __n__ and minimal degree > cn (0 < c < 1/2). We prove that (1) There exist __n__~0~ = __n__~0~(__c__) and __k__ = __k__(__c__) such that if __n__ > __n__~0~ and __G__ contains a cycle __C__~__t__~ for some __t__ > 2__k__, then __G__ contains a cycle

Long paths and large cycles in finite gr

Long paths and large cycles in finite graphs

✍ Hikoe Enomoto 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 503 KB

Cycle lengths in graphs with large minim

Cycle lengths in graphs with large minimum degree

✍ V. Nikiforov; R. H. Schelp 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 114 KB 👁 1 views

## Abstract Our main result is the following theorem. Let __k__ ≥ 2 be an integer, __G__ be a graph of sufficiently large order __n__, and __δ__(__G__) ≥ __n__/__k__. Then: __G__ contains a cycle of length __t__ for every even integer __t__ ∈ [4, __δ__(__G__) + 1]. If __G__ is nonbipartite then

Degree sums for edges and cycle lengths

Degree sums for edges and cycle lengths in graphs

✍ Brandt, Stephan; Veldman, Henk Jan 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 71 KB 👁 3 views

Let G be a graph of order n satisfying d(u) + d(v) ≥ n for every edge uv of G. We show that the circumference-the length of a longest cycle-of G can be expressed in terms of a certain graph parameter, and can be computed in polynomial time. Moreover, we show that G contains cycles of every length be