✦ LIBER ✦

Independence and hamiltonicity in 3-domination-critical graphs

✍ Scribed by Favaron, Odile; Tian, Feng; Zhang, Lei

Publisher: John Wiley and Sons
Year: 1997
Tongue: English
Weight: 144 KB
Volume: 25
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199707)25:3<173::aid-jgt1>3.0.co;2-i

No coin nor oath required. For personal study only.

✦ Synopsis

Let δ, γ, i and α be respectively the minimum degree, the domination number, the independent domination number and the independence number of a graph G. The graph G is 3-γ-critical if γ = 3 and the addition of any edge decreases γ by 1. It was conjectured that any connected 3-γ-critical graph satisfies i = γ, and is hamiltonian if δ ≥ 2. We show here that every connected 3-γ-critical graph G with δ ≥ 2 satisfies α ≤ δ + 2; if α = δ + 2 then i = γ; while if α ≤ δ + 1 then G is hamiltonian.

📜 SIMILAR VOLUMES

Domination critical graphs with higher i

Domination critical graphs with higher independent domination numbers

✍ Ao, S.; Cockayne, E.J.; MacGillivray, G.; Mynhardt, C.M. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 348 KB 👁 1 views

We show that for each k L 4 there exists a connected k-domination critical graph with independent domination number exceeding k, thus disproving a conjecture of Sumner and Blitch ( J Cornbinatorial Theory B 34 (19831, 65-76) in all cases except k = 3.

Paired-domination in graphs

✍ Haynes, Teresa W.; Slater, Peter J. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 145 KB 👁 1 views

In a graph G Å (V, E) if we think of each vertex s as the possible location for a guard capable of protecting each vertex in its closed neighborhood N[s], then ''domination'' requires every vertex to be protected. Thus, S ʚ V (G) is a dominating set if ʜ s √ S N[s] Å V (G). For total domination, eac

Toughness and hamiltonicity in almost cl

Toughness and hamiltonicity in almost claw-free graphs

✍ Broersma, H.J.; Ryj�?ek, Z.; Schiermeyer, I. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 491 KB 👁 2 views

Some known results on claw-free (Kl,3-free) graphs are generalized to the larger class of almost claw-free graphs which were introduced by RyjaEek. In particular, w e show that a 2-connected almost claw-free graph is I-tough, and that a 2-connected almost claw-free graph on n vertices is hamiltonian

Hamilton cycles in random graphs and dir

Hamilton cycles in random graphs and directed graphs

✍ Colin Cooper; Alan Frieze 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 266 KB 👁 2 views

Long cycles in critical graphs

✍ Noga Alon; Michael Krivelevich; Paul Seymour 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 57 KB 👁 2 views

Total domination in graphs with minimum

Total domination in graphs with minimum degree three

✍ Favaron, Odile; Henning, Michael A.; Mynhart, Christina M.; Puech, Jo�l 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 132 KB 👁 1 views

A set S of vertices of a graph G is a total dominating set, if every vertex of V (G) is adjacent to some vertex in S. The total domination number of G, denoted by γ t (G), is the minimum cardinality of a total dominating set of G. We prove that, if G is a graph of order n with minimum degree at leas