Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: A note on the distance-balanced property of generalized Petersen graphs. | A note on the distance-balanced property of generalized Petersen graphs Rui Yang Xinmin Hou i Ning Li Wei Zhong Department of Mathematics University of Science and Technology of China Hefei Anhui 230026 P. R. China Submitted Aug 25 2008 Accepted Nov 13 2009 Published Nov 24 2009 Mathematics Subject Classifications 05C75 05C12 Abstract 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 KlavZar and Rall Distance-balanced graphs Ann. Comb. 12 2008 71-79 conjectured that For any integer k 2 there exists a positive integer n0 such that the GP n k is not distance-balanced for every integer n no. In this note we give a proof of this conjecture. Keywords generalized Petersen graph distance-balanced graph 1 Introduction Let G be a simple undirected graph and V G E G be its vertex edge set. The distance d u v between vertices u and v of G is the length of a shortest path between u and v in G. For a pair of adjacent vertices u v G V G let Wuv denote the set of all vertices of G closer to u than to v that is Wuv x G V G d u x d v x . Similarly let uWv be the set of all vertices of G that are at the same distance to u and v that is uWv x G V G d u x d v x . A graph G is called distance-balanced if W W The work was supported by NNSF of China . 1 Corresponding author xmhou@ THE ELECTRONIC JOURNAL OF COMBINATORICS 16 2009 N33 1 holds for every pair of adjacent vertices u v G V G . Let uv be an arbitrary edge of G. Then d u x d v x G 1 0 -1 . Hence Wuv x G V G d v x d u x 1 uWv x G V G d v x d u x 0 and Wvu x G V G d v x d u x 1 form a partition of V G . The following proposition follows immediately from the above comments. Proposition 1 If Wuv V G 2 for an edge uv of G then G is not distance-balanced. Let n 3 be a positive integer and let k G 1 . n 1 n 2 . The generalized Petersen graph GP n
