✦ LIBER ✦

Long cycles in graphs with large degree sums and neighborhood unions

✍ Scribed by Van den Heuvel, J.

Publisher: John Wiley and Sons
Year: 1996
Tongue: English
Weight: 801 KB
Volume: 21
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199601)21:1<87::aid-jgt12>3.0.co;2-p

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

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.

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

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

Cyclic sums, network sharing, and restri

Cyclic sums, network sharing, and restricted edge cuts in graphs with long cycles

✍ Dieter Rautenbach; Lutz Volkmann 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 94 KB

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