Discussiones Mathematicae Graph Theory 31(2) (2011)
375-385

doi: 10.7151/dmgt.1552

## Graphs with equal domination and 2-distance domination numbers

Joanna Raczek
Department of Applied Physics and Mathematics Gdansk University of Technology Narutowicza 11/12, 80--233 Gdańsk, Poland |

## Abstract

Let G = (V,E) be a graph. The distance between two vertices u and v in
a connected graph G is the length of the shortest (u−v) path in G.
A set D ⊆ V(G) is a dominating set if every vertex of G is at
distance at most 1 from an element of D. The domination number of G is
the minimum cardinality of a dominating set of G. A set D ⊆ V(G)
is a 2-distance dominating set if every vertex of G is at distance at most 2
from an element of D. The 2-distance domination number of G is the minimum
cardinality of a 2-distance dominating set of G. We characterize all trees
and all unicyclic graphs with equal domination and 2-distance domination numbers.
**Keywords:** domination number, trees, unicyclic graphs

**2010 Mathematics Subject Classification:** 05C05, 05C69.

## References

[1] | M. Borowiecki and M. Kuzak, On the *k*-stable and *k*-dominating sets of graphs, in: Graphs, Hypergraphs and Block Systems. Proc. Symp. Zielona Góra 1976, ed. by M. Borowiecki, Z. Skupień, L. Szamkołowicz, (Zielona Góra, 1976). |

Received 18 December 2009

Revised 15 June 2010

Accepted 25 August 2010