关于图的控制数的几点注记

Some Notes on Domination Number in Graphs

一个图G=(V,E)的控制数γ(G)是V的这样一个子集D的最小基数,使得G中每一个顶点或者在D中或者和D中的一些顶点邻接。本文给出γ(G)的上界〔(|V|)/2〕的二个新的简短证明;得到k一控制临界图的控制数的下界,并讨论了图与补图间控制数的关系。

The domination number r(G) of a graph G= (V,E) is the minimum cardinality of a subset of V such that every vertex is either in the set or is adjacent to some vertices in the get.We give two new short proofs about the upper bound [|V|/2] of domination numbef in graph, obtain the inner bound of domination number in k-y criticzl graphs and discuss the relation of domination numbers between graph and its complement.