关于图的控制数Vizing's定理的推广

A generalization of Vizing's theorem of domination

对任意图G,设G的阶为n,边数为q,最大度为Δ, x」表示不大于x的最大整数,证明了G的控制数γ满足不等式q≤ [n-γ)(n-γ+2)-Δ(2n-2γ-3Δ+2)]/2」,而且也刻画了该不等式的极图特征,从而推广了Vizing's定理.

Let G be a simple graph with n vertices and q edges,and maximum degree Δ. It is proved that the domination number γ of G satisfies:q≤?[(n-γ)(n-γ+2)-Δ(2n-2γ-3Δ+2)]/ 2」. Moreover, the extremal graphs are characterized for which the equality hold.Vizing's theorem is generalized.