## Abstract

Let n ≥ 1 be an integer and let G be a graph. A set D of vertices in G is defined to be an n‐dominating set of G if every vertex of G is within distance n from some vertex of D. The minimum cardinality among all n‐dominating sets of G is called the n‐domination number of G and is denoted by γ_{n}(G). A set / of vertices in G is n‐irredundant if for every vertex x ∈ / there exists a vertex y that is within distance n from x but at distance greater than n from every vertex of / ‐ {x}. The n‐irredundance number of G, denoted by ir_{n}(G), is the minimum cardinality taken over all maximal n‐irredundant sets of vertices of G. We show that inf{ir_{n}(G)/γ_{n}(G) | G is an arbitrary finite undirected graph with neither loops nor multiple edges} = 1/2 with the infimum not being attained. Subsequently, we show that 2/3 is a lower bound on all quotients ir_{n}(T)/γ_{n}(T) in which T is a tree. Furthermore, we show that, for n ≥ 2, this bound is sharp. These results extend those of R. B. Allan and R.C. Laskar [“On Domination and Some Related Concepts in Graph Theory,” Utilitas Mathematica, Vol. 21 (1978), pp. 43–56], B. Bollobás and E. J. Cockayne [“Graph‐Theoretic Parameters Concerning Domination, Independence and Irredundance,” Journal of Graph Theory, Vol. 3 (1979), pp. 241–249], and P. Damaschke [Irredundance Number versus Domination Number, Discrete Mathematics, Vol. 89 (1991), pp. 101–104].

Original language | English |
---|---|

Pages (from-to) | 1-9 |

Number of pages | 9 |

Journal | Journal of Graph Theory |

Volume | 18 |

Issue number | 1 |

DOIs | |

Publication status | Published - Jan 1994 |

Externally published | Yes |

## ASJC Scopus subject areas

- Geometry and Topology