On the new extension of distance-balanced graphs

Document Type : Research Paper


1 Department of Mathematics‎, ‎Payame Noor University‎, ‎P.O.Box 9395-3697‎, ‎Tehran‎, ‎Iran

2 School of Mathematics‎, ‎Iran University of Science and Technology‎, ‎Narmak‎, ‎Tehran 16846-13114‎, ‎Iran

3 Department of Mathematics and Statistics‎, ‎Imam Hossein University‎, ‎Tehran‎, ‎Iran


‎In this paper‎, ‎we initially introduce the concept of $n$-distance-balanced property which is considered as the generalized concept of distance-balanced property‎. ‎In our consideration‎, ‎we also define the new concept locally regularity in order to find a connection between $n$-distance-balanced graphs and their lexicographic product‎. ‎Furthermore‎, ‎we include a characteristic method which is practicable and can be used to classify all graphs with $i$-distance-balanced properties for $ i=2,3 $ which is also relevant to the concept of total distance‎. ‎Moreover‎, ‎we conclude a connection between distance-balanced and 2-distance-balanced graphs‎.


Main Subjects

[1] 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 no. 5 (2009) 1048–1053.
[2] F. Buckley and F. Harary, Distance in Graphs, Addison-Wesley Publishing Company, Advanced Book Program, Redwood City, CA, 1990.
[3] S. Cabello and P. Luksic, The complexity of obtaining a distance-balanced graph, Electron. J. Combin., 18 no. 1 (2011) 10 pp. 34
[4] L. Chen, X. Li, M. Liu and I. Gutman, On a relation between Szeged and Wiener indices of bipartite graphs,Trans. Combin., 1 no. 4 (2012) 43–49.
[5] A. A. Dobrynin, R. Entringer and I. Gutman, Wiener index of trees: theory and applications, Acta Appl. Math., 66 no. 3 (2001) 211–249.
[6] K. Fukuda and K. Handa, Antipodal graphs and oriented matroids, Discrete Math., 111 no. 1-3 (1993) 245–256.
[7] J. A. Gallian, Dynamic Survey DS6: Graph Labeling, Electronic J. Combin., DS6, (2007) 1–58.
[8] I. Gutman and A. A. Dobrynin, The Szeged index-a success story, Graph Theory Notes N. Y., 34 (1998) 37–44.
[9] K. Handa, Bipartite graphs with balanced (a,b)-partitions, Ars Combin., 51 (1999) 113–119.
[10] A. Ilic, S. Klavzar and M. Milanovic, On distance-balanced graphs, European J. Combin., 31 no. 3 (2010) 733–737.
[11] J. Jerebic, S. Klavzar and D. F. Rall, Distance-balanced graphs, Ann. Combin., 12 no. 1 (2008) 71–79.
[12] M. H. Khalifeh, H. Yousefi-Azari, A. R. Ashrafi and S. G. Wagner, Some new results on distance-based graph invariants, European J. Combin., 30 (2009) 1149–1163.
[13] K. Kutnar, A. Malnic, D. Marusic and S. Miklavic, Distance-balanced graphs: Symmetry conditions, Discrete Math., 306 (2006) 1881–1894.
[14] K. Kutnar, A. Malnic, D. Marusic and S. Miklavic, The strongly distance-balanced property of the generalized Petersen graphs, Ars Math. Contemp., 2 no. 1 (2009) 41–47.
[15] K. Kutnar and S. Miklavic, Nicely distance-balanced graphs, European J. Combin., 39 (2014) 57–67.
[16] S. Miklavic and P. Sparl, On the connectivity of bipartite distance-balanced graphs, European J. Combin., 33 no. 2 (2012) 237–247.
[17] M. Tavakoli, H. Yousefi-Azari and A. R. Ashrafi, Note on edge distance-balanced graphs, Trans. Combin., 1 no. 1 (2012) 1–6.
[18] 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) 3 pp.