Graph‐theoretic parameters concerning domination, independence, and irredundance

Abstract

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 )⌉.