A sufficient condition for pancyclic graphs

作者：Zhao, Kewen^*; Lin, Yue; Zhang, Ping

来源：Information Processing Letters, 2009, 109(17): 991-996.

DOI：10.1016/j.ipl.2009.05.009

• Interconnection networks
• Hamiltonian paths
• Hamiltonian cycles
• Pancyclic graphs
• Sufficient conditions

In 2005, Rahman and Kaykobad proved that if G is a connected graph of order n such that d(x) + d(y) + d(x, y) >= n + 1 for each pair x, y of distinct nonadjacent vertices in G, where d(x, y) is the length of a shortest path between x and y in G, then G has a Hamiltonian path [Inform. Process. Lett. 94 (2005) 37-41]. In 2006 Li proved that if G is a 2-connected graph of order n >= 3 such that d(x) + d(y) + d(x, y) >= n + 2 for each pair x, y of nonadjacent vertices in G, then G is pancyclic or G = K-n/2.n/2 where n >= 4 is an even integer [Inform. Process. Lett. 98 (2006) 159-161]. In this work we prove that if G is a 2-connected graph of order n such that d(x) + d(y) + d(x, y) >= n + 1 for all pairs x, y of distinct nonadjacent vertices in G, then G is pancyclic or G belongs to one of four specified families of graphs.

• 出版日期2009-8-16
• 单位海南热带海洋学院