✦ LIBER ✦

Least domination in a graph

✍ Scribed by Odile Favaron

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 357 KB
Volume: 150
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(95)00180-5

No coin nor oath required. For personal study only.

✦ Synopsis

The least domination number 7L of a graph G is the minimum cardinality of a dominating set of G whose domination number is minimum. The least point covering number ~L of G is the minimum cardinality of a total point cover (point cover including every isolated vertex of G) whose total point covering number is minimum. We prove a conjecture of Sampathkumar saying that ~L ~<-~n in every connected graph of order n~2. We disprove another one saying that YL <~L in every graph but instead of it, we establish the best possible inequality 7L <~ 3~L-Finally, in relation with the minimum cardinality 7t of a dominating set without isolated vertices (total dominating set), we prove that the ratio 7L/Tt can be in general arbitrarily large, but 9 if we restrict ourselves to the class of trees. remains bounded by ~" Research partially supported by PRC Mathlnfo.

📜 SIMILAR VOLUMES

The least point covering and domination

The least point covering and domination numbers of a graph

✍ E. Sampathkumar 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 310 KB

Strong weak domination and domination ba

Strong weak domination and domination balance in a graph

✍ E. Sampathkumar; L.Pushpa Latha 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 365 KB

Stability, domination and irredundance i

Stability, domination and irredundance in a graph

✍ Odile Favaron 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 441 KB

In a graph G, a set X is called a stable set if any two vertices of X are nonadjacent. A set X is called a dominating set if every vertex of V-X is joined to at least one vertex of X. A set Xis called an irredundant set if every vertex of X, not isolated in X, has at least one proper neighbor, that

On domination and independent domination

On domination and independent domination numbers of a graph

✍ Robert B. Allan; Renu Laskar 📂 Article 📅 1978 🏛 Elsevier Science 🌐 English ⚖ 399 KB

For a graph G, the definitions of doknation number, denoted y(G), and independent domination number, denoted i(G), are given, and the following results are obtained: oorollrrg 1. For any graph G, y(L(G)) = i@(G)), where Z,(G) is the line graph of G. (This $xh!s t.lic rtsult ~(L(T))~i(L(T)), h w ere

Domination in a graph with a 2-factor

✍ Ken-ichi Kawarabayashi; Michael D. Plummer; Akira Saito 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 77 KB

## Abstract Let γ(__G__) be the domination number of a graph __G__. Reed 6 proved that every graph __G__ of minimum degree at least three satisfies γ(__G__) ≤ (3/8)|__G__|, and conjectured that a better upper bound can be obtained for cubic graphs. In this paper, we prove that a 2‐edge‐connected cu

Domination and irredundance in the queen

Domination and irredundance in the queens' graph

✍ A.P Burger; E.J Cockayne; C.M Mynhardt 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 1020 KB

The vertices of the queem;' graph {~, are the squares of an n × n chessboard and two squares are adjacent ifa queen placed on one covers the other. It is shown that the domination num;~'r of Q. is at most 31n/54 + O(1), that Q. possesses minimal dominating sets of cardina~tty 5n/2 -O(l) and that the