Domination, radius, and minimum degree

We prove sharp bounds concerning domination number, radius, order and minimum degree of a graph. In particular, we prove that if G is a connected graph of order n , domination number γ and radius r , then 2 3 r ≤ γ ≤ n − 4 3 r + 2 3 . Equality is achieved in the upper bound if, and only if, G is a p...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2009-07, Vol.157 (13), p.2964-2968
Main Authors: Henning, Michael A., Mukwembi, Simon
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Combinatorics
Combinatorics. Ordered structures
Computer science
control theory
systems
Domination
Exact sciences and technology
Mathematics
Minimum degree
Radius
Sciences and techniques of general use
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We prove sharp bounds concerning domination number, radius, order and minimum degree of a graph. In particular, we prove that if G is a connected graph of order n , domination number γ and radius r , then 2 3 r ≤ γ ≤ n − 4 3 r + 2 3 . Equality is achieved in the upper bound if, and only if, G is a path or a cycle on n vertices with n ≡ 4 ( mod 6 ) . Further, if G has minimum degree δ ≥ 3 and r ≥ 6 , then using a result due to Erdös, Pach, Pollack, and Tuza [P. Erdös, J. Pach, R. Pollack, Z. Tuza, Radius, diameter, and minimum degree. J. Combin. Theory B 47 (1989), 73–79] we show that γ ≤ n − 2 3 ( r − 6 ) δ .
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2009.04.009