具有最大控制数的连通图的刻画(英文)

Characterization of Connected Graphs with Maximum Domination Number

英文关键词:connected graph  crown  domination number  domination critical graph

中文摘要:

      设Ｇ为一个Ｐ阶图，γ（Ｇ）表示Ｇ的控制数．显然γ（Ｇ）≤［ｐ／２］．本文的目的是刻画达到这个上界的连通图．主要结果：（１）当ｐ为偶数时，γ（Ｇ）＝ｐ／２当且仅当Ｇ≈C₄或者Ｇ为某连通图的冠；（２）当ｐ为奇数时，γ（Ｇ）＝(p-1)/2当且仅当Ｇ的每棵生成树为定理３．１中所示的两类树之一．

英文摘要:

      Let G be a connected graph of order p, and let γ(G) denote the domination number of G. Clearly, γ(G) ≤[p/2]. The aim of this paper is to characterize the graphs G that reaches this upper bound. The main results are as follows: (1) when p is even, γ(G) = p/2 if and only if either G≈C₄ or G is the crown of a connected graph with p/2 vertices; (2) when p is odd, γ(G) = (p-1)/2 if and only if every spanning tree of G is one of the two classes of trees shown in Theorem 3.1.