Premium
On equality in an upper bound for domination parameters of graphs
Author(s) -
Favaron O.,
Mynhardt C. M.
Publication year - 1997
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/(sici)1097-0118(199703)24:3<221::aid-jgt3>3.0.co;2-r
Subject(s) - domination analysis , mathematics , combinatorics , upper and lower bounds , discrete mathematics , graph , mathematical analysis , vertex (graph theory)
We consider the well‐known upper bounds μ( G ) ≤| V ( G )| − Δ( G ), where Δ( G ) denotes the maximum degree of G and μ( G ) the irredundance, domination or independent domination numbers of G and give necessary and sufficient conditions for equality to hold in each case. We also describe specific classes of graphs for which equality does or does not hold and show that the difference between the domination and irredundance numbers can be arbitrary even when equality in the above bound holds for the domination number. © 1997 John Wiley & Sons, Inc.