𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Chordal graphs and upper irredundance, upper domination and independence

✍ Scribed by Michael S. Jacobson; Ken Peters

Publisher
Elsevier Science
Year
1990
Tongue
English
Weight
648 KB
Volume
86
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper we consider the following parameters: IR(G), the upper irredundance number, which is the order of the largest maximal irredundant set, I'(G), the upper domination number, which is the order of the largest minimal dominating set and /3(G), the independence number, which is the order of the largest maximal independent set.

It is well known that for any graph G, /3(G) < I-'(G) < IR(G).

In this paper we show that these parameters are equal for all chordal graphs, and a class of graphs not containing a set of forbidden subgraphs.

πŸ“œ SIMILAR VOLUMES

Vertex criticality for upper domination
Vertex criticality for upper domination and irredundance
✍ P. J. P. Grobler; C. M. Mynhardt πŸ“‚ Article πŸ“… 2001 πŸ› John Wiley and Sons 🌐 English βš– 104 KB

## Abstract Let Ο€ be any of the domination parameters __ir__ Ξ³, __i__, Ξ², Ξ“ or __IR__. The graph __G__ is π‐__critical__ (Ο€^+^‐__critical__) if the removal of any vertex of __G__ causes Ο€(__G__) to decrease (increase). We show that the classes of __IR__‐critical and Γ‐critical graphs coincide, and

The sequence of upper and lower dominati
The sequence of upper and lower domination, independence and irredundance numbers of a graph
✍ E.J. Cockayne; C.M. Mynhardt πŸ“‚ Article πŸ“… 1993 πŸ› Elsevier Science 🌐 English βš– 803 KB

Necessary and sufficient conditions are established for the existence of a graph whose upper and lower domination, independence and irredundance numbers are six given positive integers. This result shows that the only relationships between these six parameters which hold for all graphs and which do

Graph-theoretic parameters concerning do
Graph-theoretic parameters concerning domination, independence, and irredundance
✍ B. BollobΓ‘s; E. J. Cockayne πŸ“‚ Article πŸ“… 1979 πŸ› John Wiley and Sons 🌐 English βš– 402 KB

## 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 comm

Upper total domination in claw-free grap
Upper total domination in claw-free graphs
✍ Odile Favaron; Michael A. Henning πŸ“‚ Article πŸ“… 2003 πŸ› John Wiley and Sons 🌐 English βš– 114 KB

## 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__ (other than itself). The maximum cardinality of a minimal total dominating set of __G__ is the upper total domination number of __G__, denoted by Ξ“~__