𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Graph-theoretic parameters concerning domination, independence, and irredundance

✍ Scribed by B. Bollobás; E. J. Cockayne

Publisher
John Wiley and Sons
Year
1979
Tongue
English
Weight
402 KB
Volume
3
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A vertex x in a subset X of vertices of an undericted graph is redundant if its closed neighbourhood is contained in the union of closed neighborhoods of vertices of X – {x}. In the context of a communications network, this means that any vertex that may receive communications from X may also be informed from X – {x}. The irredundance number ir (G) is the minimum cardinality taken over all maximal sets of vertices having no redundancies. The domination number γ(G) is the minimum cardinality taken over all dominating sets of G, and the independent domination number i(G) is the minimum cardinality taken over all maximal independent sets of vertices of G. The paper contians results that relate these parameters. For example, we prove that for any graph G, ir (G) > γ(G)/2 and for any grpah __G__with p vertices and no isolated vertices, i(G) ≤ p‐γ(G) + 1 ‐ ⌈(p ‐ γ(G))/γ(G)⌉.

📜 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

Independence and hamiltonicity in 3-domi
Independence and hamiltonicity in 3-domination-critical graphs
✍ Favaron, Odile; Tian, Feng; Zhang, Lei 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 144 KB 👁 3 views

Let δ, γ, i and α be respectively the minimum degree, the domination number, the independent domination number and the independence number of a graph G. The graph G is 3-γ-critical if γ = 3 and the addition of any edge decreases γ by 1. It was conjectured that any connected 3-γ-critical graph satisf

The ratio of the irredundance number and
The ratio of the irredundance number and the domination number for block-cactus graphs
✍ Zverovich, V. E. 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 96 KB 👁 2 views

Let γ(G) and ir(G) denote the domination number and the irredundance number of a graph G, respectively. Allan and Laskar [Proc. 9th Southeast Conf. on Combin., Graph Theory & Comp. (1978) 43-56] and Bollobás and Cock- ayne [J. Graph Theory (1979) 241-249] proved independently that γ(G) < 2ir(G) for

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.

Model of twelve properties of a set of o
Model of twelve properties of a set of organic solvents with graph-theoretical and/or experimental parameters
✍ Lionello Pogliani 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 180 KB

## Abstract Twelve properties of a highly heterogeneous class of organic solvents have been modeled with a graph‐theoretical molecular connectivity modified (MC) method, which allows to encode the core electrons and the hydrogen atoms. The graph‐theoretical method uses the concepts of simple, gener