×

Graphs with equal domination and 2-distance domination numbers. (English) Zbl 1234.05179

Summary: Let \(G= (V,F)\) 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\subseteq 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\subseteq 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.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C12 Distance in graphs
05C05 Trees
PDFBibTeX XMLCite
Full Text: DOI Link