Premium
The ratio of the distance irredundance and domination numbers of a graph
Author(s) -
Hattingh Johannes H.,
Henning Michael A.
Publication year - 1994
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/jgt.3190180102
Subject(s) - combinatorics , mathematics , vertex (graph theory) , domination analysis , dominating set , neighbourhood (mathematics) , bound graph , connectivity , graph , upper and lower bounds , discrete mathematics , infimum and supremum , graph power , line graph , mathematical analysis
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].