On the \(r\)-domination number of a graph
type: Item
instance of: scholarly article
title: On the \(r\)-domination number of a graph
zbMATH Open document ID: 0776.05059
DOI: 10.1016/0012-365X(92)90591-3
author: J. Griggs
author: Joan P. Hutchinson
published in: Discrete Mathematics
publication date: 1993-01-16T00:00:00Z
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\).
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 89891
zbMATH Keywords: vertex degrees
zbMATH Keywords: Eulerian graph
zbMATH Keywords: \(r\)-domination number
zbMATH Keywords: distance
zbMATH Keywords: spanning tree
reviewed by: J. W. Moon
MaRDI profile type: Publication
cites work: Graphs with homeomorphically irreducible spanning trees
cites work: Q3818315
cites work: A linear algorithm for the domination number of a tree
cites work: Spanning trees in graphs of minimum degree 4 or 5
cites work: Q3801574
cites work: Spanning Trees with Many Leaves
cites work: Relations between packing and covering numbers of a tree
cites work: Domination in graphs with minimum degree two
cites work: Q3291034
cites work: R -Domination in Graphs
description: scientific article; zbMATH DE number 89891