图论中图的Dominating圈的存在

Existence of Dominating Cycle in Graphs

本文作者采用构造分析的方法研究并得到了一类非Dominating圈图的结构。在此基础上就图的两个参数研究了图的Dominating圈的存在,得到一些关于Dominating圈存在的新结果,扩大了Dominating圈图的范围,而且这些结果均比Veldman得到的更好。主要结果为:设图G是具有n(≥5)个顶点的简单图,如果对于G的任意一对分离的边e,f及对V(G)的任意非空子集S d(e)+d(f)≥n-3及ω_1(G-S)≤|S|则图G是Dominating圈图。

Graphical Dominating cycle theory has the same highly important theoretical and practical value as Graphical Hamiltonian cycle theory in graph theory.In order to explain the new contribution of the present paper, it is necessary to review concisely previous research work. Graphical Dominating cycle theory was first presented by Lesniak and Williams in 1977. From then on, many mathematians have been showing their great interest in it. In 1983, the existence of Graphical Dominating cycle graph was systematically investigated by Veldman and some sufficient conditions for its existence were obtained. As these conditions are obviovsly not always necessary there exist many dominating cycle graphs that do not satisfy them. In this paper, a new result about the existence of dominating cycle graphs is given and proved. Veldman's sufficient condition is given as d(e)+d(f)≥n-2.The author's sufficient condition is given as d(e)+d(f)≥n-3. Obviously, our sufficient condition is less severe than that of Veldman's and is therefore better.