𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Long dominating cycles in graphs

✍ Scribed by Ruqun Shen; Feng Tian

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
310 KB
Volume
177
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Let G be a connected graph of order n, and let NC2(G) denote min{ [N(u) UN(v)[:

In this paper, we prove that if G contains a dominating cycle and ~ ~> 2, then G contains a dominating cycle of length at least min{n,2NC2(G)-3}.

πŸ“œ 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.

Dominating cycles in halin graphs
Dominating cycles in halin graphs
✍ MirosΕ‚awa SkowroΕ„ska; Maciej M. SysΕ‚o πŸ“‚ Article πŸ“… 1990 πŸ› Elsevier Science 🌐 English βš– 676 KB

A cycle in a graph is dominating if every vertex lies at distance at most one from the cycle and a cycle is D-cycle if every edge is incident with a vertex of the cycle. In this paper, first we provide recursive formulae for finding a shortest dominating cycle in a Hahn graph; minor modifications ca

Dominating cycles in bipartite biclaw-fr
Dominating cycles in bipartite biclaw-free graphs
✍ Daniel Barraez; Evelyne Flandrin; Hao Li; Oscar Ordaz πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 354 KB

Flandrin et ai. (to appear) define a simple bipartite graph to be biclaw-free if it contains no induced subgraph isomorphic to H, where H could be obtained from two copies of K1.3 by adding an edge joining the two vertices of degree 3. They have shown that if G is a bipartite, balanced, biclaw-free

Dominating cycles in regular 3-connected
Dominating cycles in regular 3-connected graphs
✍ Bill Jackson; Hao Li; Yongjin Zhu πŸ“‚ Article πŸ“… 1992 πŸ› Elsevier Science 🌐 English βš– 744 KB

Jackson, B., H. Li and Y. Zhu, Dominating cycles in regular 3-connected graphs, Discrete Mathematics 102 (1992) 163-176. Let G be a 3-connected, k-regular graph on at most 4k vertices. We show that, for k > 63, every longest cycle of G is a dominating cycle. We conjecture that G is in fact hamilton