K 1,3 -Free图上的弦泛圈性

Chorded Pancyclicity on K 1,3 -Free Graph

一个非诱导圈被称为弦圈,即在图中至少有一条额外的边连接圈内两个非相邻的顶点。一个阶数为n的图G, 如果G包含长度为从4到n的弦圈,则称为弦泛圈图。1991年,R.J. Faudree, R.J. Gould和T.E. Lindquester得出结论:令G是阶数为n(n≥14)的2-连通,K1,3-free图。如果对于每一对不相邻的顶点x,y,有|N(x)∪N(y)|≥2n−23,则G是泛圈图。在本文中,我们扩展了这个结果,把泛圈性推广到弦泛圈性:对于任意2-连通,阶数为n(n≥34)的K1,3-free图G,如果每对不相邻顶点x,y∈V(G),满足|N(x)∪N(y)|≥2n−23,则图G是弦泛圈图。

A non-induced cycle is called a chorded cycle, that is, a cycle that has at least one additional edge connecting two non-consecutive vertices within the cycle. A graph G of order n is chorded pancyclic if G contains a chorded cycle of each length from 4 to n. In 1991, R.J. Faudree, R.J. Gould, and T.E. Lindquester concluded: Let G be a 2-connectedK1,3-free graph with the ordern(n≥14). If|N(x)∪N(y)|≥2n−23for each pair of nonadjacent verticesx,y, then G is pancyclic. In this paper, we extended this result by generalizing the concept of pancyclicto chorded pancyclic: ever 2-connected,K1,3-free graph G with ordern≥43is chorded pancyclic if the number of the union of for each pair of nonadjacent vertices at least2n−23.