The sequence of upper and lower domination, independence and irredundance numbers of a graph
type: Item
instance of: scholarly article
title: The sequence of upper and lower domination, independence and irredundance numbers of a graph
zbMATH Open document ID: 0788.05055
DOI: 10.1016/0012-365X(93)90288-5
author: E. J. Cockayne
author: Christina M. Mynhardt
published in: Discrete Mathematics
publication date: 1994-03-10T00:00:00Z
review text: Six numerical invariants of graphs are considered, namely the upper domination number \(\Gamma(G)\), the lower domination number \(\gamma(G)\), the upper independence number \(\beta(G)\), the lower independence number \(\text{i} (G)\), the upper irredundance number \(\text{IR} (G)\) and the lower irredundance number \(\text{ir} (G)\). The symbol \(N[x]\) for a vertex \(x\) of a graph \(G\) denotes the set consisting of \(x\) and of all vertices which are adjacent to \(x\) in \(G\). For a subset \(X\) of the vertex set \(V(G)\) of \(G\), put \(N[X]=\bigcup_{x \in X}N[x]\). A set \(D \subseteq V(G)\) is dominating, if \(N[D]=V(G)\). A set \(I \subseteq V(G)\) is independent, if no two vertices of \(I\) are adjacent in \(G\). A set \(X \subseteq V(G)\) is irredundant, if \(N[x]-N[X-\{x\}] \neq \varnothing\) for each \(x \in X\). The upper (or lower) domination number of \(G\) is the maximum (or minimum respectively) number of vertices of a minimal dominating set in \(G\). The upper (or lower) independence number of \(G\) is the maximum (or minimum respectively) number of vertices of a maximal independent set in \(G\). The upper (or lower) irredundance number of \(G\) is the maximum (or minimum respectively) number of vertices of a maximal irredundant set in \(G\). Some results concerning these numerical invariants of graphs are presented.
reviewed by: Bohdan Zelinka
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 500630
zbMATH Keywords: domination number
zbMATH Keywords: independence number
zbMATH Keywords: irredundance number
MaRDI profile type: Publication
cites work: Q3815323
cites work: Q3277097
cites work: Q5668821
cites work: Graph-theoretic parameters concerning domination, independence, and irredundance
cites work: On generalised minimal domination parameters for paths
cites work: Total domination in graphs
cites work: Contributions to the theory of domination, independence and irredundance in graphs
cites work: Towards a theory of domination in graphs
cites work: Properties of Hereditary Hypergraphs and Middle Graphs
cites work: Q4014312
cites work: Q5753985
cites work: Stability, domination and irredundance in a graph
cites work: Q3691778
cites work: Q3340900
cites work: Bibliography on domination in graphs and some basic definitions of domination parameters
cites work: Q3815322
cites work: Chordal graphs and upper irredundance, upper domination and independence
cites work: Q4346795
cites work: Q3291034
cites work: Q5284022
full work available at URL: 0012-365x(93)90288-5
OpenAlex ID: W2048864944
Wikidata QID: Q128081504
Recommended article: On the differences between the upper irredundance, upper domination and independence numbers of a graph
Recommended article: THE UPPER AND LOWER INDEPENDENCE NUMBER OF GRAPHS
Recommended article: Q4847233
Recommended article: Q4457559
Recommended article: Partial domination and irredundance numbers in graphs
Recommended article: Q3987050
Recommended article: Chordal graphs and upper irredundance, upper domination and independence
Recommended article: Cycle domination, independence, and irredundance in graphs
Recommended article: Q4326194
Recommended article: Degree sequences of graphs and dominance order
description: scientific article; zbMATH DE number 500630