THE RATIO OF THE DISTANCE IRREDUNDANCE AND DOMINATION NUMBERS OF A GRAPH

Let n greater than or equal to 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 e very vertex of G is within distance n from some vertex of D. The minim um cardinality among all n-dominating sets of G is called the n-domina tion number of G and is denoted by gamma(n)(G). A set l of vertices in G is n-irredundant if for every vertex x epsilon l there exists a ver tex y that is within distance n from x but at distance greater than n from every vertex of l - {x}. The n-irredundance number of G, denoted by ir(n)(G), is the minimum cardinality taken over all maximal n-irred undant sets of vertices of G. We show that inf{ir(n)(G)/gamma(n)(G)\G is an arbitrary finite undirected graph with neither loops nor multipl e edges} = 1/2 with the infimum not being attained. Subsequently, we s how that 2/3 is a lower bound on all quotients ir(n)(T)/gamma(n)(T) in which T is a tree. Furthermore, we show that, for n greater than or e qual to 2, this bound is sharp. These results extend those of R.B. All an and R.C. Laskar [''On Domination and Some Related Concepts in Graph Theory,'' Utilitas Mathematica, Vol, 21 (1978), pp. 43-56], B. Bollob as and E. J. Cockayne [''Graph-Theoretic Parameters Concerning Dominat ion, Independence and Irredundance,'' Journal of Graph Theory, Vol. 3 (1979), pp.241-249], and P. Damaschke [''Irredundance Number versus Do mination Number, Discrete Mathematics, Vol, 89 (1991), pp. 101-104]. ( C) 1994 John Wiley & Sons, Inc.