On equality in an upper bound for domination parameters of graphs

✍ Scribed by Favaron, O.; Mynhardt, C. M.

• Publisher: John Wiley and Sons
• Year: 1997
• Tongue: English
• Weight: 141 KB
• Volume: 24
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/(sici)1097-0118(199703)24:3<221::aid-jgt3>3.0.co;2-r

✦ Synopsis

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.