✦ LIBER ✦

Upper total domination in claw-free graphs

✍ Scribed by Odile Favaron; Michael A. Henning

Publisher: John Wiley and Sons
Year: 2003
Tongue: English
Weight: 114 KB
Volume: 44
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.10134

No coin nor oath required. For personal study only.

✦ Synopsis

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 (other than itself). The maximum cardinality of a minimal total dominating set of G is the upper total domination number of G, denoted by Γ~t~(G). We establish bounds on Γ~t~(G) for claw‐free graphs G in terms of the number n of vertices and the minimum degree δ of G. We show that $\Gamma _t(G) \le 2(n+1)/3$ if $\delta \in { 1,2}, \Gamma _t(G) \le 4n/(\delta + 3)$ if $\delta \in { 3,4}$, and $\Gamma _t(G) \le n/2$ if δ ≥ 5. The extremal graphs are characterized. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 148–158, 2003

📜 SIMILAR VOLUMES

Total domination in graphs

✍ E. J. Cockayne; R. M. Dawes; S. T. Hedetniemi 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 374 KB

Hamilton cycles in claw-free graphs

✍ Cun-Quan Zhang 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 299 KB 👁 2 views

Even Pairs in Claw-Free Perfect Graphs

✍ Cláudia Linhares Sales; Frédéric Maffray 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 424 KB

An even pair in a graph is a pair of non-adjacent vertices such that every chordless path between them has even length. A graph is called strict quasi-parity when every induced subgraph that is not a clique has an even pair, and it is called perfectly contractile when every induced subgraph can be t

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 👁 3 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

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 👁 3 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

Hamiltonian cycles in 3-connected claw-f

Hamiltonian cycles in 3-connected claw-free graphs

✍ MingChu Li 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 437 KB 👁 2 views