图中控制数的有关结论

Some results on domination in graphs

令G=(V,E)是一个图,点集S■V,如果满足N[S]=V(G)(或N(S)=V(G)),则称点集S是一个控制集(或全控制集).一个连通图G如果满足:对任何不相邻于一次点的点v,G-v的全控制数小于G的全控制数,则称图G是一个γ_t-临界图.给出了连通无爪3-正则图G的控制数满足γ(G)≤n/3.同时找到一个直径是2的4-γ_t-临界图.

Let G= （V, E） be a graph, the subset S of V is called a dominating set （or total dominating set） if N[S]=V（G） （or N（S）=V（G） ）. A graph G with no isolated vertex is total domination vertex critical if for any vertex v of G that is not adjacent to a vertex of degree one, the total domination number of G-v is less than the total domination number of G. We call these graphs γt-critical. This paper, shows that the claw-free cubic graph G satisfying γ（G） ≤ n/3 and gives a 4-γt- critical graph G with diam（G）=4.