✦ LIBER ✦

A note on distance-dominating cycles

✍ Scribed by P. Fraisse

Publisher: Elsevier Science
Year: 1988
Tongue: English
Weight: 396 KB
Volume: 71
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(88)90033-7

No coin nor oath required. For personal study only.

✦ Synopsis

Nous prouvons une conjecture due & Bondy et Fan. Un cycle C d'un graphe G est dit m-dominant si tout sommet de V(G -C) est a distance au plus m de C. Notre r&t&at est: si G est k-connexe, et si G n'a pas de cycle m-dominant, alors il existe un stable de cardinal k + 1, dont les sommets sont deux 3 distance em + 2 au moins. We prove a conjecture of Bondy and Fan. Let C denote a cycle of a graph G. We say that C is m-dominating if all the vertices of V(G -C) arc: at a distance at most m from C. Our result is: if G is k-connected and has no m-dominating cycle, then there is an independent set of cardiiality k + 1, whose vertices are pairwise at a distance at least 2m + 2.

📜 SIMILAR VOLUMES

A note on dominating cycles in 2-connect

A note on dominating cycles in 2-connected graphs

✍ D. Bauer; E. Schmeichel; H.J. Veldman 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 277 KB

A sufficient condition for dominating cy

A sufficient condition for dominating cycles

✍ J.A Bondy; Genghua Fan 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 214 KB

A note on total domination

✍ Robert B Allan; Renu Laskar; Stephen Hedetniemi 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 278 KB

For a graph G, let ~'(G), 3,z(G), i(G) and ir(G) denote the domination, total domination, independent domination and irredundance numbers of G, respectively. The following conjectures due to Robyn Dawes are proved: G)<~p and (ii) i(G)+ ~/z(G)~2. It is also shown that (iii) 3,t(G) ~<2ir(G) and (iv) 3

On the length of longest dominating cycl

On the length of longest dominating cycles in graphs

✍ Hoa Vu Dinh 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 719 KB

Vu Dinh, H., On the length of longest dominating cycles in graphs, Discrete Mathematics 121 (1993) 21 l-222. ## A cycle C in an undirected and simple graph if G contains a dominating cycle. There exists l-tough graph in which no longest cycle is dominating. Moreover, the difference of the length

A note on short cycles in diagraphs

✍ C.T Hoàng; B Reed 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 297 KB

if G is a directed graph with n vertices and minimal outdegree k, then G contains a directed cycle of length at most In~k]. This conjecture is known to be true for k ~< 3. In this paper, we present a proof of the conjecture for the cases k = 4 and k = 5. We also present a new conjecture which implie

A Note on Spectrally Dominant Norms

✍ Angel Rodriguez Palacios 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 78 KB