×

On 2-distance-balanced graphs. (English) Zbl 1404.05041

Summary: Let \(n\) denote a positive integer. A graph \(\Gamma\) of diameter at least \(n\) is said to be \(n\)-distance-balanced whenever for any pair of vertices \(u,v\) of \(\Gamma\) at distance \(n\), the number of vertices closer to \(u\) than to \(v\) is equal to the number of vertices closer to \(v\) than to \(u\). In this article we consider \(n=2\) (e.g. we consider 2-distance-balanced graphs). We show that there exist 2-distance-balanced graphs that are not 1-distance-balanced (e.g. distance-balanced). We characterize all connected 2-distance-balanced graphs that are not 2-connected. We also characterize 2-distance-balanced graphs that can be obtained as Cartesian product or lexicographic product of two graphs.

MSC:

05C12 Distance in graphs
05C76 Graph operations (line graphs, products, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A. Abiad, B. Brimkov, A. Erey, L. Leshock, X. Martinez-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:10.1016/j.dam.2017.07.010. · Zbl 1368.05035
[2] V. Andova, F. Kardoˇs and R. ˇSkrekovski, Mathematical aspects of fullerenes, Ars Math. Contemp.11 (2016), 353-379,https://amc-journal.eu/index.php/amc/article/ view/834.
[3] K. Balakrishnan, B. Breˇsar, M. Changat, S. Klavˇzar, A. Vesel and P. ˇZigert Pleterˇsek, Equal opportunity networks, distance-balanced graphs, and Wiener game, Discrete Optim. 12 (2014), 150-154, doi:10.1016/j.disopt.2014.01.002.
[4] K. Balakrishnan, M. Changat, I. Peterin, S. ˇSpacapan, P. ˇSparl and A. R. Subhamathi, Strongly distance-balanced graphs and graph products, European J. Combin. 30 (2009), 1048-1053, doi:10.1016/j.ejc.2008.09.018. · Zbl 1185.05052
[5] A. Behmaram, T. Doˇsli´c and S. Friedland, Matchings in m-generalized fullerene graphs, Ars Math. Contemp.11 (2016), 301-313,https://amc-journal.eu/index.php/amc/ article/view/882. · Zbl 1355.05193
[6] S. Cabello and P. Lukˇsiˇc, The complexity of obtaining a distance-balanced graph, Electron. J. Combin.18 (2011), #P49,http://www.combinatorics.org/ojs/index.php/ eljc/article/view/v18i1p49.
[7] M. Faghani, E. Pourhadi and H. Kharazi, On the new extension of distance-balanced graphs, Trans. Comb.5 (2016), 21-34, doi:10.22108/toc.2016.15048. · Zbl 1463.05133
[8] B. Frelih, Razliˇcni vidiki povezave regularnosti v grafih, Ph.D. thesis, University of Primorska, 2014, in Slovene.
[9] K. Handa, Bipartite graphs with balanced (a, b)-partitions, Ars Combin. 51 (1999), 113-119, http://www.combinatorialmath.ca/arscombinatoria/vol51.html. · Zbl 0977.05039
[10] T. Hilado and K. Nomura, Distance degree regular graphs, J. Comb. Theory Ser. B 37 (1984), 96-100, doi:10.1016/0095-8956(84)90050-9. · Zbl 0567.05028
[11] A. Ili´c, S. Klavˇzar and M. Milanovi´c, On distance-balanced graphs, European J. Combin. 31 (2010), 733-737, doi:10.1016/j.ejc.2009.10.006.
[12] J. Jerebic, S. Klavˇzar and D. F. Rall, Distance-balanced graphs, Ann. Comb. 12 (2008), 71-79, doi:10.1007/s00026-008-0337-2. · Zbl 1154.05026
[13] K. Kutnar, A. Malniˇc, D. Maruˇsiˇc and ˇS. Miklaviˇc, Distance-balanced graphs: Symmetry conditions, Discrete Math. 306 (2006), 1881-1894, doi:10.1016/j.disc.2006.03.066.
[14] K. Kutnar, A. Malniˇc, D. Maruˇsiˇc and ˇS. Miklaviˇc, Matchings in m-generalized fullerene graphs, Ars Math. Contemp. 2 (2009), 41-47,https://amc-journal.eu/index. php/amc/article/view/75.
[15] K. Kutnar and ˇS. Miklaviˇc, Nicely distance-balanced graphs, European J. Combin. 39 (2014), 57-67, doi:10.1016/j.ejc.2013.12.002. · Zbl 1284.05084
[16] ˇS. Miklaviˇc and P. ˇSparl, On the connectivity of bipartite distance-balanced graphs, European J. Combin.33 (2012), 237-247, doi:10.1016/j.ejc.2011.10.002.
[17] ˇS. Miklaviˇc and P. ˇSparl, ‘-distance-balanced graphs, 2017,arXiv:1702.05257 [math.CO].
[18] N. Tratnik and P. ˇZigert Pleterˇsek, Resonance graphs of fullerenes, Ars Math. Contemp. 11 (2016), 425-435,https://amc-journal.eu/index.php/amc/article/view/ 1000.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.