Small step-dominating sets in trees

DOI10.1016/J.DISC.2006.07.038MaRDI QIDQ870988zbMATH OpenOpenAlexFDO

Authors Frédéric Maffray, Dieter Rautenbach

Publication date 15 March 2007

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2006.07.038

zbMATH Keywords

diameterstep-dominating set

Mathematics Subject Classification ID

Trees (05C05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Review text

The paper proves that for every tree \(T\) of diameter \(D\geq 3\) there is a set \(S\subseteq V(T)\) with \(| S| =D-1\) and a mapping st \(: S\rightarrow \{0,1,2,...\} \) such that for every vertex \(v\in V(T)\) there is exactly one vertex \(u\in S\) whose distance to \(v\) equals st\((u)\). This settles a conjecture of \textit{G. Dror, A. Lev}, and \textit{Y. Roditty} [Discrete Math. 289, 137--144 (2004; Zbl 1055.05112)].

Recommendations

• A note: Some results in step domination of trees
• Spanning trees with small diameters
• scientific article; zbMATH DE number 1792592
• A distinct distance set of 9 nodes in a tree of diameter 36
• On exact \(n\)-step domination

Cites work

• A note: Some results in step domination of trees
• scientific article; zbMATH DE number 1792592 (Why is no real title available?)
• scientific article; zbMATH DE number 2197935 (Why is no real title available?)

Cited in

(2)

• A distinct distance set of 9 nodes in a tree of diameter 36
• A note: Some results in step domination of trees

This page was built for publication: Small step-dominating sets in trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q870988)