Premium
Graph‐theoretic parameters concerning domination, independence, and irredundance
Author(s) -
Bollobás B.,
Cockayne E. J.
Publication year - 1979
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190030306
Subject(s) - combinatorics , neighbourhood (mathematics) , mathematics , vertex (graph theory) , domination analysis , dominating set , graph , discrete mathematics , independence number , connectivity , mathematical analysis
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 )⌉.