Discussiones Mathematicae Graph Theory 31(2) (2011)
Graphs with equal domination and 2-distance domination numbers
Department of Applied Physics and Mathematics
Gdansk University of Technology
Narutowicza 11/12, 80--233 Gdańsk, Poland
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.
|||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