数学
学位(音乐)
组合数学
半径
计算机科学
物理
声学
计算机安全
作者
Michael A. Henning,Simon Mukwembi
标识
DOI:10.1016/j.dam.2009.04.009
摘要
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 ) δ .
科研通智能强力驱动
Strongly Powered by AbleSci AI