Irredundance number versus domination number

✍ Scribed by Peter Damaschke

• Book ID: 103058298
• Publisher: Elsevier Science
• Year: 1991
• Tongue: English
• Weight: 243 KB
• Volume: 89
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(91)90403-o

✦ Synopsis

Damaschke, P., Irredundance number versus domination number, Discrete Mathematics 89 (1991) 101-104. The domination number y(G) and the irredundance number ir(G) of a graph G have been considered by many authors from a graph-theoretic or from an algorithmic point of view. In this graph-theoretic paper the infimum of all quotients ir(G)/y(G) is investigated.

It is well known that ir(G) s y(G) holds for all undirected graphs G. We show that f is the infimum of all quotients ir(T)/y(T) in which T is a tree. Furthermore, there is no tree that attains the infimum. An analogous result for graphs is already known.