2024/07/02 by Ma, Gang, Wang, Jianfeng, Klavžar, Sandi
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2407.02635
A connected graph G of diameter \rm diam(G) ≥ ℓ is ℓ-distance-balanced if |Wxy|=|Wyx| for every x,y∈ V(G) with dG(x,y)=ℓ, where Wxy is the set of vertices of G that are closer to x than to y. It is proved that if k≥ 3 and n>k(k+2), then the generalized Petersen graph GP(n,k) is not distance-balanced and that GP(k(k+2),k) is distance-balanced. This significantly improves the main result of Yang et al. [Electron. J. Combin. 16 (2009) #N33]. It is also proved that if k≥ 6, where k is even, and n>(5)/(4)k2+2k, or if k≥ 5, where k is odd, and n>(7)/(4)k2+(3)/(4)k, then GP(n,k) is not 2-distance-balanced. These results partially resolve a conjecture of Miklavič and Šparl [Discrete Appl. Math. 244 (2018) 143--154].