关于支配圈和支配路的存在性

ON THE EXISTENCE OF DOMINATING CYCLES AND DOMINATING PATHS

圈C称为图G的支配圈,若对G中任一点v,至少有圈C上的一个顶点与之邻接.类似定义图G的支配路.本文讨论了图中支配圈和支配路的存在性,得到下列结果:(1)设G是有n个顶点,ε条边的k-连通图(k≥1),若ε>((n-k)/2)~2-(3n-k)/2+4,则G中存在支配圈.(2)设G是有n个顶点的k-连通图(k≥2),若对图G中任何有k个顶点的独立点集{v_0,v_1,…v_(k-1)},满足N(v_i)∩N(v^i)=φ(0≤i≠i≤k-1),有^(k-1)∑_(i=0)d(v_i)>n-2(k+2)成立,则G中存在支配路.

A cycle C of a graph G is called a dominating cycle if every vertex of G is adjacent to one vertex of C at least. A dominating path, is defined analogously. In this Paper, we discuss the existence of dominating cycles and dominating paths in a graph G and obtain the following results: (1) Let G be k-connected graph of order n (k≥1) with more than((n-k)/2)~2-(3n-k)/2+4 edges, then the graph G contains dominating cycles. (2) Let G be a k-connected graph (k≥2) of order n such that, for every k independent vertices {v_0,v_1,…v_(k-1)}with N(v_i)∩N(v_i)=φ(0≤i≠j≤k-1), ??d(v_i)>n-2(k+2),then there exist dominating paths contained in the graph G.