✦ LIBER ✦

Cycles and paths in graphs with large minimal degree

✍ Scribed by V. Nikiforov; R. H. Schelp

Publisher: John Wiley and Sons
Year: 2004
Tongue: English
Weight: 114 KB
Volume: 47
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20015

No coin nor oath required. For personal study only.

✦ Synopsis

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 C~t − 2__s__~ for some positive s < k; (2) Let G be 2‐connected and nonbipartite. For each ε(0 < ε < 1), there exists n~0~ = n~0~(c,ε) such that if n ≥ n~0~ then G contains a cycle C~t~ for all t with $\left \lceil { 2\over c}\right \rceil -2\leq t\leq 2(1-\varepsilon) cn$. This answers positively a question of Erdős, Faudree, Gyárfás and Schelp. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 39–52, 2004

📜 SIMILAR VOLUMES

The longest cycle of a graph with a larg

The longest cycle of a graph with a large minimal degree

✍ Noga Alon 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 214 KB 👁 1 views

We show that every graph G on n vertices with minimal degree at least n / k contains a cycle of length at least [ n / ( k -111. This verifies a conjecture of Katchalski. When k = 2 our result reduces t o the classical theorem of Dirac that asserts that if all degrees are at least i n then G is Hamil

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

Cycles and paths in edge-colored graphs

Cycles and paths in edge-colored graphs with given degrees

✍ A. Abouelaoualim,; K. Ch. Das; W. Fernandez de la Vega; M. Karpinski; Y. Manouss 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 203 KB 👁 1 views

## Abstract Sufficient degree conditions for the existence of properly edge‐colored cycles and paths in edge‐colored graphs, multigraphs and random graphs are investigated. In particular, we prove that an edge‐colored multigraph of order __n__ on at least three colors and with minimum colored degre

Long dominating cycles and paths in grap

Long dominating cycles and paths in graphs with large neighborhood unions

✍ H. J. Broersma; H. J. Veldman 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 413 KB 👁 1 views

## Abstract Let __G__ be a graph of order __n__ and define __NC(G)__ = min{|__N__(__u__) ∪ __N__(__v__)| |__uv__ ∉ __E__(__G__)}. A cycle __C__ of __G__ is called a __dominating cycle__ or __D__‐__cycle__ if __V__(__G__) ‐ __V__(__C__) is an independent set. A __D__‐__path__ is defined analogously.

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.

Parity theorems for paths and cycles in

Parity theorems for paths and cycles in graphs

✍ J. A. Bondy; F. Y. Halberstam 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 294 KB 👁 1 views

We extend an elegant proof technique of A . G . Thomason, and deduce several parity theorems for paths and cycles in graphs. For example, a graph in which each vertex is of even degree has an even number of paths if and only if it is of even order, and a graph in which each vertex is of odd degree h