A lower bound for the distance k-domination number of trees

DOI10.1007/BF03323033MaRDI QIDQ2581114zbMATH OpenFDO

Authors Dirk Meierling, Lutz Volkmann

Publication date 13 January 2006

Published in Results in Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF03323033

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Review text

The distance \(k\)-domination number \(\gamma_k(G)\) of a graph \(G\) is the size of the smallest subset \(D\) of nodes of \(G\) such that any node not in \(D\) has distance at most \(k\) from at least one node in \(D\). The authors show that if \(T\) is a tree with \(n\) nodes and \(t\) end-nodes, then \((2k+1)\gamma_k(T)\geq n+2k-kt\); and they characterize the trees for which equality holds.

Recommendations

• Lower bound on the distance k-domination number of a tree
• Distance domination and distance irredundance in graphs
• scientific article; zbMATH DE number 1123784
• The minimum eccentric distance sum of trees with given distance k-domination number
• Distance-k locating-dominating sets in graphs

Cites work

• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• Lower bound on the distance k-domination number of a tree
• Lower bound on the domination number of a tree
• On packing and covering numbers of graphs
• Relations between packing and covering numbers of a tree

Cited in

(13)

• A linear-time algorithm for minimum \(k\)-hop dominating set of a cactus graph
• Domination on hyperbolic graphs
• Distance domination in graphs with given minimum and maximum degree
• Distance domination in graphs
• m-dominating k-ended trees of graphs
• scientific article; zbMATH DE number 1123784 (Why is no real title available?)
• Distance domination in vertex partitioned graphs
• scientific article; zbMATH DE number 5174847 (Why is no real title available?)
• Lower bound on the distance k-domination number of a tree
• Sublinear-space streaming algorithms for estimating graph parameters on sparse graphs
• The d-distance p-packing domination number: complexity, cycles, and trees
• Revisiting d-distance (independent) domination in trees and in bipartite graphs
• A note on neighborhood total domination in graphs

This page was built for publication: A lower bound for the distance \(k\)-domination number of trees

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