控制临界图

Domination Critical Graphs

一个顶点集S称为图G的控制集,如果对每一个V(?)S,有一个顶点u∈S,使u与v邻接.任何这样的控制集的最小基数称为G的控制数,记为γ(G).对G中每一对不连接的顶点u,v,有γ(G+uv)<γ(G)=k,称G是k-γ临界图.本文研究k-γ临界图的一些性质,特别对3-γ临界图得到下列结果:(1)对直径为3的3-γ临界图证明Sumner猜想,即γ(G)等于G的独立控制数;(2)任何一个正则3-γ临界图,其直径必为2.

A set of vertices S is said to dominate the graph G if for each v∈S, there is a vertex u6S with u adjacent to v. The smallest cardinality of any such dominating set is called the domination number of G and is denoted by γ(G). For each u, v∈V(G) with u not adjacent to y, y(G +uv)<γ(G) = k, G is k-γ critical graph. In this paper, some properties of k-γ critical graphs are studied. Particularly, following results in 3-γ critical graphs are shown : (1) For 3-γ critical graph G, we show the Sumner conjecture if G has-diameter 3 . (2) The diameter of every regular 3-γ critical graph is 2.