✦ LIBER ✦

A characterization of domination perfect graphs

✍ Scribed by I. E. Zverovich; V. E. Zverovich

Publisher: John Wiley and Sons
Year: 1991
Tongue: English
Weight: 224 KB
Volume: 15
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190150202

No coin nor oath required. For personal study only.

✦ Synopsis

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 of domination perfect graphs.

Bollobis and Cockayne [4] proved an inequality relating y( G) and i( G) for the class of K1,k -free graphs. It is shown that the same inequality holds for a wider class of graphs.

All graphs will be finite and undirected without loops or multiple edges.

For undefined terms see [5].

A dominating set of a graph G = (V, E) is a subset D of V such that each vertex of V -D is adjacent to at least one vertex of D. An independent

📜 SIMILAR VOLUMES

A note on the characterization of domina

A note on the characterization of domination perfect graphs

✍ Jason Fulman 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 191 KB

## Abstract A graph __G__ is domination perfect if for each induced subgraph __H__ of __G__, γ(__H__) = __i__(__H__), where γ and __i__ are a graph's domination number and independent domination number, respectively. Zverovich and Zverovich [3] offered a finite forbidden induced characterization of

A semi-induced subgraph characterization

A semi-induced subgraph characterization of upper domination perfect graphs

✍ Zverovich, Igor E.; Zverovich, Vadim E. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 324 KB 👁 2 views

Let β(G) and Γ(G) be the independence number and the upper domination number of a graph G, respectively. A graph G is called Γ-perfect if β(H) = Γ(H), for every induced subgraph H of G. The class of Γ-perfect graphs generalizes such well-known classes of graphs as strongly perfect graphs, absorbantl

Independent perfect domination sets in C

Independent perfect domination sets in Cayley graphs

✍ Jaeun Lee 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 92 KB 👁 1 views

## Abstract In this paper, we show that a Cayley graph for an abelian group has an independent perfect domination set if and only if it is a covering graph of a complete graph. As an application, we show that the hypercube __Q~n~__ has an independent perfect domination set if and only if __Q~n~__ i

A Characterization of b-Perfect Graphs

✍ Chính T. Hoàng; Frédéric Maffray; Meriem Mechebbek 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 316 KB

## Abstract A b‐coloring is a coloring of the vertices of a graph such that each color class contains a vertex that has a neighbor in all other color classes, and the b‐chromatic number of a graph __G__ is the largest integer __k__ such that __G__ admits a b‐coloring with __k__ colors. A graph is b

k-Bounded classes of dominant-independen

k-Bounded classes of dominant-independent perfect graphs

✍ Zverovich, Igor E. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 253 KB 👁 2 views

Let α(G), γ(G), and i(G) be the independence number, the domination number, and the independent domination number of a graph G, respectively. For any k ≥ 0, we define the following hereditary classes: αi where ISub(G) is the set of all induced subgraphs of a graph G. In this article, we present a f

A generalization of perfect graphs?i-per

A generalization of perfect graphs?i-perfect graphs

✍ Cai, Leizhen; Corneil, Derek 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 1003 KB

Let i be a positive integer. We generalize the chromatic number x ( G ) of G and the clique number w(G) of G as follows: The i-chromatic number of G , denoted by x Z ( G ) , is the least number k for which G has a vertex partition V,, V,, . . . , Vk: such that the clique number of the subgraph induc