Revista de la
Unión Matemática Argentina
On certain regular nicely distance-balanced graphs
Blas Fernández, Štefko Miklavič, and Safet Penjić
Volume 65, no. 1 (2023), pp. 165–185    

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

Download PDF

Abstract

A connected graph $\Gamma$ is called nicely distance-balanced, whenever there exists a positive integer $\gamma=\gamma(\Gamma)$ such that, for any two adjacent vertices $u,v$ of $\Gamma$, there are exactly $\gamma$ vertices of $\Gamma$ which are closer to $u$ than to $v$, and exactly $\gamma$ vertices of $\Gamma$ which are closer to $v$ than to $u$. Let $d$ denote the diameter of $\Gamma$. It is known that $d \le \gamma$, and that nicely distance-balanced graphs with $\gamma = d$ are precisely complete graphs and cycles of length $2d$ or $2d+1$. In this paper we classify regular nicely distance-balanced graphs with $\gamma=d+1$.

References

  1. A. Abedi, M. Alaeiyan, A. Hujdurović, and K. Kutnar, Quasi-$\lambda$-distance-balanced graphs, Discrete Appl. Math. 227 (2017), 21–28. MR 3661412.
  2. 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. MR 3189033.
  3. K. Balakrishnan, M. Changat, I. Peterin, S. Špacapan, P. Šparl, and A. Subhamathi, Strongly distance-balanced graphs and graph products, European J. Combin. 30 (2009), no. 5, 1048–1053. MR 2513907.
  4. A. E. Brouwer, A. M. Cohen, and A. Neumaier, Distance-Regular Graphs, Ergebnisse der Mathematik und ihrer Grenzgebiete (3), 18, Springer, Berlin, 1989. MR 1002568.
  5. F. C. Bussemaker, S. Čobeljić, D. M. Cvetković, and J. J. Seidel, Computer Investigation of Cubic Graphs, T. H. Report 76-WSK-01, Department of Mathematics, Technological University Eindhoven, The Netherlands, 1976.
  6. S. Cabello and P. Lukšič, The complexity of obtaining a distance-balanced graph, Electron. J. Combin. 18 (2011), no. 1, Paper 49, 10 pp. MR 2776825.
  7. M. Cavaleri and A. Donno, Distance-balanced graphs and travelling salesman problems, Ars Math. Contemp. 19 (2020), no. 2, 311–324. MR 4183154.
  8. B. Frelih and Š. Miklavič, On 2-distance-balanced graphs, Ars Math. Contemp. 15 (2018), no. 1, 81–95. MR 3862079.
  9. K. B. Guest, J. M. Hammer, P. D. Johnson, and K. J. Roblee, Regular clique assemblies, configurations, and friendship in edge-regular graphs, Tamkang J. Math. 48 (2017), no. 4, 301–320. MR 3734623.
  10. K. Handa, Bipartite graphs with balanced $(a,b)$-partitions, Ars Combin. 51 (1999), 113–119. MR 1675124.
  11. A. Hujdurović, On some properties of quasi-distance-balanced graphs, Bull. Aust. Math. Soc. 97 (2018), no. 2, 177–184. MR 3772645.
  12. A. Ilić, S. Klavžar, and M. Milanović, On distance-balanced graphs, European J. Combin. 31 (2010), no. 3, 733–737. MR 2587025.
  13. J. Jerebic, S. Klavžar, and D. F. Rall, Distance-balanced graphs, Ann. Comb. 12 (2008), no. 1, 71–79. MR 2401137.
  14. J. Jerebic, S. Klavžar, and G. Rus, On $\ell$-distance-balanced product graphs, Graphs Combin. 37 (2021), no. 1, 369–379. MR 4197386.
  15. K. Kutnar, A. Malnič, D. Marušič, and Š. Miklavič, Distance-balanced graphs: symmetry conditions, Discrete Math. 306 (2006), no. 16, 1881–1894. MR 2251569.
  16. K. Kutnar and Š. Miklavič, Nicely distance-balanced graphs, European J. Combin. 39 (2014), 57–67. MR 3168514.
  17. Š. Miklavič and P. Šparl, On the connectivity of bipartite distance-balanced graphs, European J. Combin. 33 (2012), no. 2, 237–247. MR 2854645.
  18. Š. Miklavič and P. Šparl, $\ell$-distance-balanced graphs, Discrete Appl. Math. 244 (2018), 143–154. MR 3802543.
  19. M. Tavakoli, F. Rahbarnia, and A. R. Ashrafi, Further results on distance-balanced graphs, Politehn. Univ. Bucharest Sci. Bull. Ser. A Appl. Math. Phys. 75 (2013), no. 1, 77–84. MR 3032544.