The conjecture on distance-balancedness of generalized Petersen graphs holds when internal edges have jumps $3$ or $4$

Ma, Gang (author), Wang, JianFeng (author), Klavžar, Sandi (author)

A connected graph $G$ with ${\rm diam}(G) \ge \ell$ is $\ell$-distance-balanced if $|W_{xy}|=|W_{yx}|$ for every $x,y\in V(G)$ with $d_{G}(x,y)=\ell$, where $W_{xy}$ is the set of vertices of $G$ that are closer to $x$ than to $y$. Miklavič and Šparl [Discrete Appl. Math. 244 (2018), 143--154] conjectured that if $n > n_k$ where where $n_k = 11$ if $k = 2$, $n_k = (k+1)^2$ if $k$ is odd, and $n_k = k(k +2)$ if $k \ge 4$ is even, then the generalized Petersen graph $GP(n,k)$ is not $\ell$-distance-balanced for any $1\le \ell<{\rm diam}(GP(n,k))$. In the seminal paper, the conjecture was verified for $k=2$. In this paper we prove that the conjecture holds for $k=3$ and for $k=4$.

• Language: English
• Keywords: distance-balanced graph, $\ell$-distance-balanced graph, generalized Petersen graph, diameter
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FMF - Faculty of Mathematics and Physics
• Publication status: Published
• Publication version: Version of Record
• Publication date: 01.01.2025
• Year: 2025
• Number of pages: Str. 703-733
• Numbering: Vol. 68, no. 2
• PID: 20.500.12556/RUL-175773
• UDC: 519.17
• ISSN on article: 1669-9637
• DOI: 10.33044/revuma.4824
• COBISS.SI-ID: 256284675
• Publication date in RUL: 07.11.2025

Record is a part of a journal

• Title: Revista de la Unión Matemática Argentina
• Shortened title: Rev. Unión Mat. Argent.
• Publisher: Unión Matemática Argentina
• ISSN: 1669-9637
• COBISS.SI-ID: 524760345

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.

Secondary language

• Language: Slovenian
• Keywords: razdaljno uravnoteženi graf, $\ell$-razdaljno uravnoteženi graf, posplošeni Petersenov graf, premer