Maximum values of Szeged index and edge-Szeged index of graphs

The Szeged index is a graph invariant which is a natural generalization of Wiener index. In this note, we disprove two recent conjectures concerning with the maximum value of Szeged index of graphs, which are due to Khalifeh et al. (Europ. J. Combinatorics (2008), doi:10.1016/j.ejc.2008.09.019) and respectively, to Gutman et al. (Groat. Chem. Acta 81 (2)(2008) 263–266) and prove a conjecture on Szeged index due to Klavzar et al. ( Appl. Math. Lett. 9 (1996), 45–49), which states that the complete bipartite graph K ⌈ n 2 ⌉ , ⌈ n 2 ⌉ has maximum Szeged index among all connected graphs on n vertices. The last conjecture is previously proved by Dobrynin (Croat. Chem. Acta 70(3), 819-825), but our proof turns out to be much simpler and self-contained.