泛圈图的一个新的充分条件

A New Sufficient Condition for Pancyclic Graphs

设G是一个阶为n的 2连通简单图 ,αv 表示G中包含点v的最大独立集的点数 ,对任意uv∈/E ,设Tuv=V \(N(u)∪N(v) ) ,αuv=min{αu,αv}.本文证明了 :如果对于任一对不相邻点u ,v,N(u)∩N(v)≥min{αuv- 1 ,Tuv },则除一些特殊图外 ,对于G的任一点x和任意整数k(4≤k≤n) 。

Let G be a 2 connected simple graph of order n and α v denote the order of the largest independent set containing the vertex v in G . For any uv∈/ E, let T uv =V\(N(u)∪N(v)),α uv = min{ α u,α v} . This paper proves that if for any non adjacent vertices u,v, N(u)∩N(v) ≥ min{ α uv -1,T uv }, then there exists cycle G of length k such that G contains vertex x for any vertex x and any k(4≤k≤n), except some special graphs.