On certain regular nicely distance-balanced graphs

Authors

  • Blas Fernández University of Primorska, Andrej Marušič Institute, Muzejski trg 2, 6000 Koper, Slovenia
  • Štefko Miklavič University of Primorska, Andrej Marušič Institute, Muzejski trg 2, 6000 Koper, Slovenia; and Institute of Mathematics, Physics, and Mechanics, Jadranska 19, 1000 Ljubljana, Slovenia
  • Safet Penjić University of Primorska, Andrej Marušič Institute, Muzejski trg 2, 6000 Koper, Slovenia

DOI:

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

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$.

Downloads

Download data is not yet available.

References

A. Abedi, M. Alaeiyan, A. Hujdurović, and K. Kutnar, Quasi-λ-distance-balanced graphs, Discrete Appl. Math. 227 (2017), 21–28. MR 3661412.

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.

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.

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.

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.

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.

M. Cavaleri and A. Donno, Distance-balanced graphs and travelling salesman problems, Ars Math. Contemp. 19 (2020), no. 2, 311–324. MR 4183154.

B. Frelih and Š. Miklavič, On 2-distance-balanced graphs, Ars Math. Contemp. 15 (2018), no. 1, 81–95. MR 3862079.

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.

K. Handa, Bipartite graphs with balanced $(a,b)$-partitions, Ars Combin. 51 (1999), 113–119. MR 1675124.

A. Hujdurović, On some properties of quasi-distance-balanced graphs, Bull. Aust. Math. Soc. 97 (2018), no. 2, 177–184. MR 3772645.

A. Ilić, S. Klavžar, and M. Milanović, On distance-balanced graphs, European J. Combin. 31 (2010), no. 3, 733–737. MR 2587025.

J. Jerebic, S. Klavžar, and D. F. Rall, Distance-balanced graphs, Ann. Comb. 12 (2008), no. 1, 71–79. MR 2401137.

J. Jerebic, S. Klavžar, and G. Rus, On ℓ-distance-balanced product graphs, Graphs Combin. 37 (2021), no. 1, 369–379. MR 4197386.

K. Kutnar, A. Malnič, D. Marušič, and Š. Miklavič, Distance-balanced graphs: symmetry conditions, Discrete Math. 306 (2006), no. 16, 1881–1894. MR 2251569.

K. Kutnar and Š. Miklavič, Nicely distance-balanced graphs, European J. Combin. 39 (2014), 57–67. MR 3168514.

Š. Miklavič and P. Šparl, On the connectivity of bipartite distance-balanced graphs, European J. Combin. 33 (2012), no. 2, 237–247. MR 2854645.

Š. Miklavič and P. Šparl, ℓ-distance-balanced graphs, Discrete Appl. Math. 244 (2018), 143–154. MR 3802543.

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.

Downloads

Published

2023-06-13

Issue

Vol. 65 No. 1 (2023)

Section

Article

License

Copyright (c) 2023 Blas Fernández, Štefko Miklavič, Safet Penjić

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

Authors who publish with this journal agree to the following terms:

Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal. The Journal may retract the paper after publication if clear evidence is found that the findings are unreliable as a result of misconduct or honest error.