论文部分内容阅读
图的支配问题是近年来图论中一个比较活跃的研究领域，有很多实际的应用。1981年Cockayne等人证明计算任意图的支配数是一个NP困难问题。对于一些特殊图，Dewdney证明了计算二分图的支配数是一个NP困难问题；Booth等人证明了计算弦图的支配数是一个NP困难问题；Yannakakis等人证明了计算线图的支配数是一个NP困难问题。研究和支配数相关的临界问题，对于解决一般的NP困难问题，有重要的理论意义。 图的支配问题中有一个很重要的分支就是图的支配临界问题。图的支配临界问题主要分为两大类，一类是图的支配边临界问题，另一类是图的支配点临界问题。本文主要运用计算机计算与数学推理证明相结合的方法，针对支配边临界图，研究其哈密顿性质和最小边数性质。 Wojcicka猜想所有3连通，4支配边临界的图都是哈密顿图，并进一步猜想(k-1)连通的，k支配边临界的图都是哈密顿图。本文构造了一类3连通4支配边临界的非哈密顿图，从而证明k=4时Wojcicka猜想不成立。 f(n，k)表示具有n个顶点的k支配边临界图的最小边数。对于k=1和k=2，易知：Sumner猜想本文对奇数和偶数分别构造了k支配边临界图，给出了f(n，k)的一个上界：