Further Remarks on n-Distance-Balanced Graphs

Morteza Faghani, Ehsan Pourhadi


Throughout this paper, we present a new strong property of graph so-
called nicely n-distance-balanced which is notably stronger than the concept of n-
distance-balanced recently given by the authors. We also initially introduce a new
graph invariant which modies Szeged index and is suitable to study n-distance-
balanced graphs. Looking for the graphs extremal with respect to the modied
Szeged index it turns out the n-distance-balanced graphs with odd integer n are
the only bipartite graphs which can maximize the modied Szeged index and this
also disproves a conjecture proposed by Khalifeh et al. [Khalifeh M.H.,Youse-
Azari H., Ashra A.R., Wagner S.G.: Some new results on distance-based graph
invariants, European J. Combin. 30 (2009) 1149-1163]. Furthermore, we gather
some facts concerning with the nicely n-distance-balanced graphs generated by some
well-known graph products. To enlighten the reader some examples are provided.
Moreover, a conjecture and a problem are presented within the results of this article.


Nicely n-distance-balanced, Szeged index, lexicographic, Cartesian and strong products.

Full Text:



Aouchiche, M. and Hansen, P., "On a conjecture about the Szeged index", European J.

Combin. 31 (2010) 1662-1666.

Chiniforooshan, E. and Wu, B., "Maximum values of Szeged index and edge-Szeged index of

graphs", Electron. Notes Discrete Math. 34 (2009) 405-409.

Dobrynin, A.A. and Gutman, I., "On a graph invariant related to the sum of all distances in

a graph", Publ. Inst. Math. (Beograd) 56 (1994), 18-22.

Faghani, M. and Ashra, A.R., "Revised and edge revised Szeged indices of graphs", Ars

Math. Contemp. 7 (2014) 153-160.

Faghani, M., Pourhadi, E. and Kharazi, H., "On the new extension of distance-balanced

graphs", Trans. Combin. 5:4 (2016), 21-34.

Gutman, I., "A formula for the Wiener number of trees and its extension to graphs containing

cycles", Graph Theory Notes New York 27 (1994), 9-15.

Hammack, R., Imrich, W. and Klavzar, S., Handbook of product graphs, CRC Press, Taylor

Francis Group, 2011.

Ilic, A., Klavzar, S. and Milanovic, M., "On distance-balanced graphs", European J. Combin.

(2010) 733-737.

Jerebic, J., Klavzar, S. and Rall, D.F., "Distance-balanced graphs", Ann. Combin. 12:1

(2008), 71-79.

Khalifeh, M.H.,Youse-Azari, H., Ashra, A.R. and Wagner, S.G., "Some new results on

distance-based graph invariants", European J. Combin. 30 (2009) 1149-1163.

Kutnar, K., Malnic, A., Marusic, D. and Miklavic, S., "Distance-balanced graphs: Symmetry

conditions", Discrete Math. 306 (2006) 1881-1894.

Kutnar, K., Malnic, A., Marusic, D. and Miklavic, S., "The strongly distance-balanced prop-

erty of the generalized Petersen graphs", Ars Math. Contemp. 2 (2009) 41-47.

Kutnar, K. and Miklavic, S., "Nicely distance-balanced graphs", European J. Combin. 39

(2014) 57-67.

Miklavic, S. and Sparl, P., "On the connectivity of bipartite distance-balanced graphs",

European J. Combin. 33 (2012) 237-247.

Tavakoli, M., Youse-Azari, H. and Ashra, A.R., "Note on edge distance-balanced graphs",

Trans. Combin. 1:1 (2012), 1-6.

DOI: https://doi.org/10.22342/jims.25.1.563.44-61


  • There are currently no refbacks.

Journal of the Indonesian Mathematical Society
Mathematics Department, Universitas Gadjah Mada
Senolowo, Sinduadi, Mlati, Sleman Regency, Special Region of Yogyakarta 55281, Telp. (0274) 552243
Email: jims.indoms@gmail.com

p-ISSN: 2086-8952 | e-ISSN: 2460-0245

Journal of the Indonesian Mathematical Society is licensed under a Creative Commons Attribution 4.0 International License

web statistics
View My Stats