✦ LIBER ✦

A note on the characterization of domination perfect graphs

✍ Scribed by Jason Fulman

Publisher: John Wiley and Sons
Year: 1993
Tongue: English
Weight: 191 KB
Volume: 17
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190170106

No coin nor oath required. For personal study only.

✦ Synopsis

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 domination perfect graphs. This characterization is not correct, but the ideas in [3] can be used to weaken the known sufficient conditions for a graph to be domination perfect and to obtain short proofs of some results regarding domination perfect graphs. © 1993 John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

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

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

A note on Ki-perfect graphs

✍ Jason I. Brown; Derek G. Corneil; A. Ridha Mahjoub 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 348 KB

## Abstract __Ki__‐perfect graphs are a special instance of __F ‐ G__ perfect graphs, where __F__ and __G__ are fixed graphs with __F__ a partial subgraph of __G.__ Given __S__, a collection of __G__‐subgraphs of graph __K__, an __F ‐ G__ cover of __S__ is a set of __T__ of __F__‐subgraphs of __K__

Note: The diameter of edge domination cr

Note: The diameter of edge domination critical graphs

✍ Matteo Paris 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 111 KB

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

On the domination of the products of gra

On the domination of the products of graphs II: Trees

✍ Michael S. Jacobson; Lael F. Kinch 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 377 KB

For a graph G, a subset of vertices D is a dominating set if for each vertex x not in D, x is adjacent to at least one vertex of D. The domination number, y(G), is the order of the smallest such set. An outstanding conjecture in the theory of domination is for any two graph G and H,