关于图的支配划分的两个猜测

Cockayne于一九七六年在美国密西根大学举行的国际《图论及其应用》会议上提出两个问题:(1)若图G的团图K(G)为奇圈,是否有c(G)≤d(G),(2)若团图K(G)为二部图,是否有c(G)≤d(G)。一九七七年,Cockayne和Hedetniemi将上述问题以猜测形式发表。本文对猜测1提出了反例,对猜测2给出了证明。 一、定义 对任一图G=(V,E),及集合,若对每一顶点,存在顶点u∈T,使得u与υ邻接,则集合T称为图G的支配集。