✦ LIBER ✦

Domination in a graph with a 2-factor

✍ Scribed by Ken-ichi Kawarabayashi; Michael D. Plummer; Akira Saito

Publisher: John Wiley and Sons
Year: 2006
Tongue: English
Weight: 77 KB
Volume: 52
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20142

No coin nor oath required. For personal study only.

✦ Synopsis

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 cubic graph G of girth at least 3__k__ satisfies $\gamma (G)\le (({3k+2}))/({9k+3})|G|$. For $k\ge 3$, this gives $\gamma (G)\le ({11}/{30})|G|$, which is better than Reed's bound. In order to obtain this bound, we actually prove a more general theorem for graphs with a 2‐factor. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 1–6, 2006

📜 SIMILAR VOLUMES

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

K4−-factor in a graph

✍ Ken-ichi Kawarabayashi 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 194 KB

## Abstract Let __G__ be a graph of order 4__k__ and let δ(__G__) denote the minimum degree of __G__. Let __F__ be a given connected graph. Suppose that |__V__(__G__)| is a multiple of |__V__(__F__)|. A spanning subgraph of __G__ is called an __F__‐factor if its components are all isomorphic to __F

Two sufficient conditions for a 2-factor

Two sufficient conditions for a 2-factor in a bipartite graph

✍ P. Katerinis 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 186 KB 👁 1 views

Total domination in 2-connected graphs a

Total domination in 2-connected graphs and in graphs with no induced 6-cycles

✍ Michael A. Henning; Anders Yeo 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 272 KB 👁 1 views

## 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__. The minimum cardinality of a total dominating set of __G__ is the total domination number γ~t~(__G__) of __G__. It is known [J Graph Theory 35 (2000)

Domination in planar graphs with small d

Domination in planar graphs with small diameter

✍ Wayne Goddard; Michael A. Henning 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 199 KB

## Abstract MacGillivray and Seyffarth (J Graph Theory 22 (1996), 213–229) proved that planar graphs of diameter two have domination number at most three and planar graphs of diameter three have domination number at most ten. They also give examples of planar graphs of diameter four having arbitrar

A characterization of domination perfect

A characterization of domination perfect graphs

✍ I. E. Zverovich; V. E. Zverovich 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 224 KB

Let u(G) and i(G) be the domination number and independent domination number of a graph G. respectively. Sumner and Moore [8] define a graph G to be domination perfect if y( H) = i( H), for every induced subgraph H of G. In this article, we give a finite forbidden induced subgraph characterization o