Revista de la
Unión Matemática Argentina
The conjecture on distance-balancedness of generalized Petersen graphs holds when internal edges have jumps 3 or 4
Gang Ma, Jianfeng Wang, and Sandi Klavžar

Volume 68, no. 2 (2025), pp. 703–733    

Published online (final version): October 8, 2025

https://doi.org/10.33044/revuma.4824

Download PDF

Abstract

A connected graph $G$ with $\mathrm{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 $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 $\mathrm{GP}(n,k)$ is not $\ell$-distance-balanced for any $1\le \ell < \mathrm{diam}(\mathrm{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$.

References

  1. A. Abiad, B. Brimkov, A. Erey, L. Leshock, X. Martínez-Rivera, S. O, S.-Y. Song, and J. Williford, On the Wiener index, distance cospectrality and transmission-regular graphs, Discrete Appl. Math. 230 (2017), 1–10.  DOI  MR  Zbl
  2. A. Ali and T. Došlić, Mostar index: Results and perspectives, Appl. Math. Comput. 404 (2021), Paper No. 126245.  DOI  MR  Zbl
  3. K. Balakrishnan, B. Brešar, M. Changat, S. Klavžar, A. Vesel, and P. Žigert Pleteršek, Equal opportunity networks, distance-balanced graphs, and Wiener game, Discrete Optim. 12 (2014), 150–154.  DOI  MR  Zbl
  4. K. Balakrishnan, M. Changat, I. Peterin, S. Špacapan, P. Šparl, and A. R. Subhamathi, Strongly distance-balanced graphs and graph products, European J. Combin. 30 no. 5 (2009), 1048–1053.  DOI  MR  Zbl
  5. S. Cabello and P. Lukšič, The complexity of obtaining a distance-balanced graph, Electron. J. Combin. 18 no. 1 (2011), Paper 49.  DOI  MR  Zbl
  6. M. Cavaleri and A. Donno, Distance-balanced graphs and travelling salesman problems, Ars Math. Contemp. 19 no. 2 (2020), 311–324.  DOI  MR  Zbl
  7. B. Fernández and A. Hujdurović, On some problems regarding distance-balanced graphs, European J. Combin. 106 (2022), Paper No. 103593.  DOI  MR  Zbl
  8. B. Fernández, Š. Miklavič, and S. Penjić, On certain regular nicely distance-balanced graphs, Rev. Un. Mat. Argentina 65 no. 1 (2023), 165–185.  DOI  MR  Zbl
  9. B. Frelih, Različni vidiki povezavne regularnosti v grafih, Ph.D. thesis, University of Primorska, Koper, 2014. Available at https://hdl.handle.net/20.500.12556/RUP-8929.
  10. B. Frelih and Š. Miklavič, On 2-distance-balanced graphs, Ars Math. Contemp. 15 no. 1 (2018), 81–95.  DOI  MR  Zbl
  11. K. Handa, Bipartite graphs with balanced $(a,b)$-partitions, Ars Combin. 51 (1999), 113–119.  MR  Zbl
  12. A. Ilić, S. Klavžar, and M. Milanović, On distance-balanced graphs, European J. Combin. 31 no. 3 (2010), 733–737.  DOI  MR  Zbl
  13. J. Jerebic, S. Klavžar, and D. F. Rall, Distance-balanced graphs, Ann. Comb. 12 no. 1 (2008), 71–79.  DOI  MR  Zbl
  14. J. Jerebic, S. Klavžar, and G. Rus, On $\ell$-distance-balanced product graphs, Graphs Combin. 37 no. 1 (2021), 369–379.  DOI  MR  Zbl
  15. K. Kutnar, A. Malnič, D. Marušič, and Š. Miklavič, Distance-balanced graphs: Symmetry conditions, Discrete Math. 306 no. 16 (2006), 1881–1894.  DOI  MR  Zbl
  16. K. Kutnar, A. Malnič, D. Marušič, and Š. Miklavič, The strongly distance-balanced property of the generalized Petersen graphs, Ars Math. Contemp. 2 no. 1 (2009), 41–47.  DOI  MR  Zbl
  17. K. Kutnar and Š. Miklavič, Nicely distance-balanced graphs, European J. Combin. 39 (2014), 57–67.  DOI  MR  Zbl
  18. G. Ma, J. Wang, and S. Klavžar, On distance-balanced generalized Petersen graphs, Ann. Comb. 28 no. 1 (2024), 329–349.  DOI  MR  Zbl
  19. Š. Miklavič and P. Šparl, On the connectivity of bipartite distance-balanced graphs, European J. Combin. 33 no. 2 (2012), 237–247.  DOI  MR  Zbl
  20. Š. Miklavič and P. Šparl, $\ell$-distance-balanced graphs, Discrete Appl. Math. 244 (2018), 143–154.  DOI  MR  Zbl
  21. R. Yang, X. Hou, N. Li, and W. Zhong, A note on the distance-balanced property of generalized Petersen graphs, Electron. J. Combin. 16 no. 1 (2009), Note 33.  DOI  MR  Zbl