Non-ℓ-distance-balanced generalized Petersen graphs GP(n,3) and GP(n,4)

2023/09/05 by Ma, Gang, Wang, Jianfeng, Klavžar, Sandi
#05C12 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2309.01900

Abstract

A connected graph G of diameter \rm diam(G) ≥ ℓ is ℓ-distance-balanced if |W_xy|=|W_yx| for every x,y∈ V(G) with d_G(x,y)=ℓ, where W_xy is the set of vertices of G that are closer to x than to y. We prove that the generalized Petersen graph GP(n,3) where n>16 is not ℓ-distance-balanced for any 1≤ ℓ < \rm diam(GP(n,3)), and GP(n,4) where n>24 is not ℓ-distance-balanced for any 1≤ ℓ < \rm diam(GP(n,4)). This partially solves a conjecture posed by Š. Miklavič and P. Šparl (Discrete Appl. Math. 244:143-154, 2018).

Related

• On distance-balanced generalized Petersen graphs
• On \1,2\-distance-balancedness of generalized Petersen graphs
• ℓ-distance-balanced graphs
• Distance-balanced graphs: symmetry conditions
• On ℓ-distance-balancedness of cubic Cayley graphs of dihedral groups