A note on the distance-balanced property of generalized Petersen graphs

作者：Yang Rui; Hou Xinmin^*; Li Ning; Zhong Wei

来源：Electronic Journal of Combinatorics, 2009, 16(1): N33.

• generalized Petersen graph
• distance-balanced graph

A graph G is said to be distance-balanced if for any edge uv of G, the number of vertices closer to u than to v is equal to the number of vertices closer to v than to u. Let GP(n,k) be a generalized Petersen graph. Jerebic, Klavazar, and Rall [Distance-balanced graphs, Ann. Comb. 12 (2008) 71-79] conjectured that: For any integer k >= 2, there exists a positive integer n(0) such that the GP(n,k) is not distance-balanced for every integer n >= n(0). In this note, we give a proof of this conjecture.

• 出版日期2009-11-24
• 单位中国科学技术大学