Cycles in Generalized Petersen Graphs
报告人:张赞波教授,广东财经大学 时间:2019年11月11日(周一)10:30
摘要:Cycles in regular graphs, particularly 3-connected cubic graphs are of specialinterets to the research community. Generalized Petersen graphs, denoted by GP(n,k), are highly symmetric $3$-connected cubic graphs that have been  investigated from many aspects. The problem of existence of Hamiltonian cycles in GP(n,k) has been studied for a long time and thoroughly settled. Inspired by Bondy's meta-conjecture that almost every nontrivial condition for Hamiltonicity also implies pancyclicity, we seek for more cycle structures in this class of graphs, by figuring out the possible lengths of cycles in them.
It turns out that generalized Petersen graphs, though not generally pancyclic, miss only very few lengths of cycles. For k∈{2,3}, we completely determine all possible cycle lengths in GP(n,k). We also obtain some results on cycle lengths of GP(n,k) where $k$ is odd. In particular, when k is odd, and n is even and sufficiently large, GP(n,k) is bipartite and weakly even pancyclic.