On a relation between Szeged and Wiener indices of bipartite graphs

نویسندگان
Chen, Lilly ID 1
Liu, Mengmeng ID 2
Li, Xueliang ID 3
Gutman, Ivan ID 4

1 Nankai University, Center for Combinatorics

2 Nankai University, Center for Combinatorics

3 Nankai University

4 University of Kragujevac Kragujevac, Serbia

doi
10.22108/toc.2012.2450
چکیده

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‎.

کلیدواژه‌ها
distance (in graph), Szeged index, Wiener index