Discussiones Mathematicae Graph Theory 31(2) (2011) 375-385
doi: 10.7151/dmgt.1552

[BIBTex] [PDF] [PS]

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