On a relation between Szeged and Wiener indices of bipartite graphs

Document Type : Research Paper

Authors

1 Nankai University, Center for Combinatorics

2 Nankai University

3 University of Kragujevac Kragujevac, Serbia

Abstract

Hansen et‎. ‎al.‎, ‎using the AutoGraphiX software‎ ‎package‎, ‎conjectured that the Szeged index $Sz(G)$ and the‎
‎Wiener index $W(G)$ of a connected bipartite graph $G$ with $n \geq‎ ‎4$ vertices and $m \geq n$ edges‎, ‎obeys the relation‎ ‎$Sz(G)-W(G) \geq 4n-8$‎. ‎Moreover‎, ‎this bound would be the best possible‎. ‎This paper offers a proof to this conjecture‎.

Keywords

Main Subjects


M. Aouchiche and P. Hansen (2010). On a conjecture about the Szeged index. European J. Combin.. 31, 1662-1666 M. Arezoomand and B. Taeri (2010). Applications of generalized hierarchical product of graphs in computing the Szeged index of chemical graphs. MATCH Commun. Math. Comput. Chem.. 64, 591-602 J. A. Bondy and U. S. R. Murty (2008). Graph Theory. Springer, Berlin. A. Dobrynin, R. Entringer and I. Gutman (2001). Wiener index of trees: theory and applications. Acta Appl. Math.. 66, 211-249 A. Dolati, I. Motevalian and A. Ehyaee (2010). Szeged index, edge Szeged index, and semi--star trees. Discrete Appl. Math.. 158, 876-881 R. C. Entringer (1997). Distance in graphs: Trees. J. Combin. Math. Combin. Comput.. 24, 65-84 I. Gutman (1994). A formula for the Wiener number of trees and its extension to graphs containing cycles. Graph Theory Notes N. Y.. 27, 9-15 I. Gutman and A. A. Dobrynin (1998). The Szeged index -- a success story. Graph Theory Notes N. Y.. 34, 37-44 I. Gutman and B. Furtula (Eds.) (2012). Distance in Molecular Graphs -- Theory. Univ. Kragujevac, Kragujevac. I. Gutman and B. Furtula (Eds.) (2012). Distance in Molecular Graphs -- Applications\/. Univ. Kragujevac, Kragujevac. I. Gutman and O. E. Polansky (1986). Mathematical Concepts in Organic Chemistry. Springer, Berlin. P. Hansen (2010). Computers and conjectures in chemical graph theory. Plenanry talk at the International Conference on Mathematical Chemistry, August 4-7, Xiamen, China. H. Hua and S. Zhang (2011). A unified approach to extremal trees with respect to geometric--arithmetic, Szeged, and edge Szeged indices. MATCH Commun. Math. Comput. Chem.. 65, 691-704 A. Ili\'c (2010). Note on PI and Szeged indices. Math. Comput. Modelling. 52, 1570-1576 X. Li, X. Yang, G. Wang and R. Hu (2012). The vertex PI and Szeged indices of chain graphs. MATCH Commun. Math. Comput. Chem.. 68, 349-356 M. J. Nadjafi--Arani, H. Khodashenas and A. R. Ashrafi (2011). On the differences between Szeged and Wiener indices of graphs. Discrete Math.. 311, 2233-2237 M. J. Nadjafi--Arani, H. Khodashenas and A. R. Ashrafi (2012). Graphs whose Szeged and Wiener numbers differ by 4 and 5. Math. Comput. Modelling. 55, 1644-1648 T. Pisanski and M. Randi\'c (2010). Use of the Szeged index and the revised Szeged index for meauring network bipartivity. Discrete Appl. Math.. 158, 1936-1944 S. Simi\'c, I. Gutman and V. Balti\'c (2000). Some graphs with extremal Szeged index. Math. Slovaca. 50, 1-15 H. Wiener (1947). Structural determination of paraffin boiling points. J. Am. Chem. Soc.. 69, 17-20 B. Zhou, X. Cai and Z. Du (2010). On Szeged indices of unicyclic graphs. MATCH Commun. Math. Comput. Chem.. 63, 113-132
Volume 1, Issue 4 - Serial Number 4
December 2012
Pages 43-49
  • Receive Date: 10 January 2013
  • Revise Date: 18 January 2013
  • Accept Date: 18 January 2013
  • Published Online: 01 December 2012