控制圆点临界图的若干性质

Some characters of domination dot-critical graphs

对于图G,如果收缩任意一条边,它的控制数下降,则称图G是圆点临界图.如果粘贴图G中任意两个顶点,它的控制数下降,则称图G是全圆点临界图.证明了对于k-正则图,当k为奇数时不存在2-全圆点临界图;当k为偶数时当且仅当此图为k+2阶图时其为2-全圆点临界图.还对是否存在不含临界点的-全圆点临界图(k≥4)进行了研究,并得出结论:存在不含临界点的4-全圆点临界图和5-全圆点临界图.

A graph G is dot-critical if contracting any edge decreases the domination number. It is totally dot-critical if identifying any two vertices decreases the domination number. This paper shows that for any k-regular graph, if k is odd, there doesn＇t exist a 2-totally dot-critical graph; if k is even, the graph is 2-totally dot-critical if and only if the number of vertices in the graph is k＋2. It also studies for each k≥4,whether exists a k-totally dot-critical graph with no critical vertices and obtain a result： there exists a 4-totally dot-critical graph and a 5-totally dot-critical graph with no critical vertices.