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

A generalization of Vizing's theorem of domination

作　　者：齐登记[1] 梁希泉[1] 

机构地区：[1]青岛科技大学数理系,山东青岛266061

出　　处：《东北师大学报（自然科学版）》2005年第1期24-27,共4页Journal of Northeast Normal University(Natural Science Edition)

基　　金：国家自然科学基金资助项目(19971034)

摘　　要：　对任意图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.

关 键 词：控制集 控制数 极图 

分 类 号：O157.5[理学—数学]