$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是弦泛圈图。

Abstract: 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.