✦ LIBER ✦

Long dominating cycles and paths in graphs with large neighborhood unions

✍ Scribed by H. J. Broersma; H. J. Veldman

Publisher: John Wiley and Sons
Year: 1991
Tongue: English
Weight: 413 KB
Volume: 15
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190150106

No coin nor oath required. For personal study only.

✦ Synopsis

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. The following result is proved: if G is 2‐connected and contains a D‐cycle, then G contains a D‐cycle of length at least min{n, 2__NC__(G)} unless G is the Petersen graph. By combining this result with a known sufficient condition for the existence of a D‐cycle, a common generalization of Ore's Theorem and several recent “neighborhood union results” is obtained. An analogous result on long D‐paths is also established.

📜 SIMILAR VOLUMES

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

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

Subdivisions of large complete bipartite

Subdivisions of large complete bipartite graphs and long induced paths in k-connected graphs

✍ Thomas Böhme; Bojan Mohar; Riste Škrekovski; Michael Stiebitz 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 67 KB 👁 1 views

## Abstract It is proved that for every positive integers __k__, __r__ and __s__ there exists an integer __n__ = __n__(__k__,__r__,__s__) such that every __k__‐connected graph of order at least __n__ contains either an induced path of length __s__ or a subdivision of the complete bipartite graph __

Total domination in 2-connected graphs a

Total domination in 2-connected graphs and in graphs with no induced 6-cycles

✍ Michael A. Henning; Anders Yeo 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 272 KB 👁 1 views

## Abstract A set __S__ of vertices in a graph __G__ is a total dominating set of __G__ if every vertex of __G__ is adjacent to some vertex in __S__. The minimum cardinality of a total dominating set of __G__ is the total domination number γ~t~(__G__) of __G__. It is known [J Graph Theory 35 (2000)

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