Main Article Content
Abstract
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.
Keywords
Article Details
References
- 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.
References
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.