PDF
Discussiones Mathematicae Graph Theory 31(2) (2011)
375-385
DOI: https://doi.org/10.7151/dmgt.1552
Graphs with equal domination and 2-distance domination numbers
| Joanna Raczek
Department of Applied Physics and Mathematics |
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
Close