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

• Gang Ma ^[1] ; Jianfeng Wang ^[1] ; Sandi Klavžar ^[2]
  1. [1] Shandong University of Technology

     Shandong University of Technology

     China

     
  2. [2] University of Ljubljana

     University of Ljubljana

     Eslovenia

     
• Localización: Revista de la Unión Matemática Argentina, ISSN 0041-6932, ISSN-e 1669-9637, Vol. 68, Nº. 2, 2025, págs. 703-733
• Idioma: inglés
• DOI: 10.33044/revuma.4824
• Enlaces
  • Texto completo
• Resumen

  • A connected graph G with 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. Miklaviˇc and Sparl [Discrete ˇ Appl. Math. 244 (2018), 143–154] conjectured that if n > nk, where nk = 11 if k = 2, nk = (k + 1)2 if k is odd, and nk = k(k + 2) if k ≥ 4 is even, then the generalized Petersen graph GP(n, k) is not ℓ-distance-balanced for any 1 ≤ ℓ < 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.

• Referencias bibliográficas
  • 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...
  • A. Ali and T. Doˇslic´, Mostar index: Results and perspectives, Appl. Math. Comput. 404 (2021), Paper No. 126245. DOI MR Zbl
  • K. Balakrishnan, B. Breˇsar, M. Changat, S. Klavˇzar, A. Vesel, and P. Zigert Pleter ˇ ˇsek, Equal opportunity networks, distance-balanced...
  • K. Balakrishnan, M. Changat, I. Peterin, S. Spacapan ˇ , P. Sparl ˇ , and A. R. Subhamathi, Strongly distance-balanced graphs and graph products,...
  • S. Cabello and P. Lukˇsicˇ, The complexity of obtaining a distance-balanced graph, Electron. J. Combin. 18 no. 1 (2011), Paper 49. DOI MR...
  • M. Cavaleri and A. Donno, Distance-balanced graphs and travelling salesman problems, Ars Math. Contemp. 19 no. 2 (2020), 311–324. DOI MR Zbl
  • B. Fernandez ´ and A. Hujdurovic´, On some problems regarding distance-balanced graphs, European J. Combin. 106 (2022), Paper No. 103593....
  • B. Fernandez ´ , S. Miklavi ˇ cˇ, and S. Penjic´, On certain regular nicely distance-balanced graphs, Rev. Un. Mat. Argentina 65 no. 1 (2023),...
  • B. Frelih, Razliˇcni vidiki povezavne regularnosti v grafih, Ph.D. thesis, University of Primorska, Koper, 2014. Available at https://hdl.handle.net/20.500.12556/RUP-8929.
  • B. Frelih and S. Miklavi ˇ cˇ, On 2-distance-balanced graphs, Ars Math. Contemp. 15 no. 1 (2018), 81–95. DOI MR Zbl
  • K. Handa, Bipartite graphs with balanced (a, b)-partitions, Ars Combin. 51 (1999), 113–119. MR Zbl
  • A. Ilic´, S. Klavˇzar, and M. Milanovic´, On distance-balanced graphs, European J. Combin. 31 no. 3 (2010), 733–737. DOI MR Zbl
  • J. Jerebic, S. Klavˇzar, and D. F. Rall, Distance-balanced graphs, Ann. Comb. 12 no. 1 (2008), 71–79. DOI MR Zbl
  • J. Jerebic, S. Klavˇzar, and G. Rus, On ℓ-distance-balanced product graphs, Graphs Combin. 37 no. 1 (2021), 369–379. DOI MR Zbl
  • K. Kutnar, A. Malnicˇ, D. Maruˇsicˇ, and S. Miklavi ˇ cˇ, Distance-balanced graphs: Symmetry conditions, Discrete Math. 306 no. 16 (2006),...
  • K. Kutnar, A. Malnicˇ, D. Maruˇsicˇ, and S. Miklavi ˇ cˇ, The strongly distance-balanced property of the generalized Petersen graphs, Ars...
  • K. Kutnar and S. Miklavi ˇ cˇ, Nicely distance-balanced graphs, European J. Combin. 39 (2014), 57–67. DOI MR Zbl
  • G. Ma, J. Wang, and S. Klavˇzar, On distance-balanced generalized Petersen graphs, Ann. Comb. 28 no. 1 (2024), 329–349. DOI MR Zbl
  • S. Miklavi ˇ cˇ and P. Sparl ˇ , On the connectivity of bipartite distance-balanced graphs, European J. Combin. 33 no. 2 (2012), 237–247....
  • S. Miklavi ˇ cˇ and P. Sparl ˇ , ℓ-distance-balanced graphs, Discrete Appl. Math. 244 (2018), 143–154. DOI MR Zbl
  • 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....