✦ LIBER ✦

Independent perfect domination sets in Cayley graphs

✍ Scribed by Jaeun Lee

Publisher: John Wiley and Sons
Year: 2001
Tongue: English
Weight: 92 KB
Volume: 37
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.1016

No coin nor oath required. For personal study only.

✦ Synopsis

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~ is a regular covering of the complete graph K~n+1~ if and only if n = 2^m^ − 1 for some natural number m. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 213–219, 2001

📜 SIMILAR VOLUMES

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

Set domination in graphs

✍ E. Sampathkumar; L. Pushpa Latha 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 355 KB

## Abstract Let __G__ = (__V, E__) be a connected graph. A set __D__ ⊂ __V__ is a __set‐dominating set__ (sd‐set) if for every set __T__ ⊂ __V__ − __D__, there exists a nonempty set __S__ ⊂ __D__ such that the subgraph 〈__S__ ∪ __T__〉 induced by __S__ ∪ __T__ is connected. The set‐domination number

Maximal independent sets in bipartite gr

Maximal independent sets in bipartite graphs

✍ Jiuqiang Liu 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 458 KB 👁 1 views

## Abstract A maximal independent set of a graph __G__ is an independent set that is not contained properly in any other independent set of __G.__ In this paper, we determine the maximum number of maximal independent sets among all bipartite graphs of order __n__ and the extremal graphs as well as

Independent sets in random sparse graphs

✍ Pedro G. Gazmuri 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 418 KB

Independent Dominating Sets and a Second

Independent Dominating Sets and a Second Hamiltonian Cycle in Regular Graphs

✍ Carsten Thomassen 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 241 KB

In 1975, John Sheehan conjectured that every Hamiltonian 4-regular graph has a second Hamiltonian cycle. Combined with earlier results this would imply that every Hamiltonian r-regular graph (r 3) has a second Hamiltonian cycle. We shall verify this for r 300.

Dominating Sets in Planar Graphs

✍ Lesley R. Matheson; Robert E. Tarjan 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 174 KB