On the r-domination number of a graph

DOI10.1016/0012-365X(92)90591-3MaRDI QIDQ1197015zbMATH OpenFDO

Authors J. Griggs, Joan P. Hutchinson

Publication date 16 January 1993

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(92)90591-3

zbMATH Keywords

\(r\)-domination numberdistanceEulerian graphspanning treevertex degrees

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45)

Review text

If \(r>0\) the \(r\)-domination number of a graph \(G_ n\) is the size \(d_ r\) of a smallest set of vertices such that every vertex of \(G\) is within distance \(r\) of a vertex in that set. The authors show, among other things, that if \(G\) has a spanning tree with at least \(n/2\) leaves then \(d_ r\leq\max\{n/(2r),1\}\). They conjecture that if the graph \(G_ n\) is Eulerian then \(d_ r\leq\lceil n/(2r)\rceil\).

Recommendations

• scientific article; zbMATH DE number 1191211
• scientific article; zbMATH DE number 4204373
• Some upper bounds related with domination number
• On domination numbers of Cartesian products of paths
• Strong non split \(r\)-domination number of a graph

Cites work

• R -Domination in Graphs
• A linear algorithm for the domination number of a tree
• Domination in graphs with minimum degree two
• Graphs with homeomorphically irreducible spanning trees
• scientific article; zbMATH DE number 3172309 (Why is no real title available?)
• scientific article; zbMATH DE number 4068901 (Why is no real title available?)
• scientific article; zbMATH DE number 4089545 (Why is no real title available?)
• Relations between packing and covering numbers of a tree
• Spanning trees in graphs of minimum degree 4 or 5
• Spanning Trees with Many Leaves

Cited in

(15)

• The rati of the irredundance and domination number of a graph
• On the domination number of a graph
• Distance \(r\)-domination number and \(r\)-independence complexes of graphs
• Some new results on distance \(k\)-domination in graphs
• On the domination number of a graph defined by containment
• scientific article; zbMATH DE number 5844276 (Why is no real title available?)
• An algorithm for the inverse distance-2 dominating set of a graph
• scientific article; zbMATH DE number 4204373 (Why is no real title available?)
• scientific article; zbMATH DE number 5717271 (Why is no real title available?)
• scientific article; zbMATH DE number 1191211 (Why is no real title available?)
• r-domination problems on homogeneously orderable graphs
• scientific article; zbMATH DE number 1750102 (Why is no real title available?)
• Higher independence complexes of graphs and their homotopy types
• On Rall's 1/2-conjecture on the domination game
• On the L-Grundy domination number of a graph

This page was built for publication: On the \(r\)-domination number of a graph

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