×

Distance domination versus iterated domination. (English) Zbl 1246.05113

Summary: A \(k\)-dominating set in a graph \(G\) is a set \(S\) of vertices such that every vertex of \(G\) is at distance at most \(k\) from some vertex of \(S\). Given a class \(\mathcal D\) of finite simple graphs closed under connected induced subgraphs, we completely characterize those graphs \(G\) in which every connected induced subgraph has a connected \(k\)-dominating subgraph isomorphic to some \(D\in \mathcal D\). We apply this result to prove that the class of graphs hereditarily \(\mathcal D\)-dominated within distance \(k\) is the same as the one obtained by iteratively taking the class of graphs hereditarily dominated by the previous class in the iteration chain. This strong relation does not remain valid if the initial hereditary restriction on \(\mathcal D\) is dropped.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C40 Connectivity
05C12 Distance in graphs
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bacsó, G., Complete description of forbidden subgraphs in the structural domination problem, Discrete Math., 309, 2466-2472 (2009) · Zbl 1210.05093
[2] Bacsó, G.; Tálos, A.; Tuza, Zs., Graph domination in distance two, Discuss. Math. Graph Theory, 25, 121-128 (2005) · Zbl 1076.05057
[3] Bacsó, G.; Tuza, Zs., Structural domination in graphs, Ars Combinatoria, 63, 235-256 (2002) · Zbl 1072.05553
[4] Borowiecki, M.; Broere, I.; Frick, M.; Mihók, P.; Semanišin, G., Survey of hereditary properties of graphs, Discuss. Math. Graph Theory, 17, 5-50 (1997) · Zbl 0902.05026
[5] Henning, M. A., Distance domination in graphs, (Haynes, T. W.; etal., Domination in Graphs: Advanced Topics (1998), Marcel Dekker: Marcel Dekker New York), 321-349 · Zbl 0891.05045
[6] Attila Tálos, On 2-dominating subgraphs, Master Thesis, Eötvös L. University, Budapest, 1992, 2-domináns részgráfokról (in Hungarian).; Attila Tálos, On 2-dominating subgraphs, Master Thesis, Eötvös L. University, Budapest, 1992, 2-domináns részgráfokról (in Hungarian).
[7] Tuza, Zs., Hereditary domination in graphs: characterization with forbidden induced subgraphs, SIAM J. Discrete Math., 22, 849-853 (2008) · Zbl 1181.05074
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.