On a relation between the Szeged index and the Wiener index for bipartite graphs

2012/10/24 by Lily Chen, Xueliang Li, Chen, Lily +3 · 1 citation
Mathematics · #05C12 #05C35 #05C90 #92E10 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C12 #msc:05C35 #msc:05C90 #msc:92E10

paper · pdf · doi:10.48550/arxiv.1210.6460

8 pages

arxiv created 2012/10/24 · arxiv updated 2012/10/25

Abstract

\small The Wiener index W(G) of a graph G is the sum of the distances between all pairs of vertices in the graph. The Szeged index Sz(G) of a graph G is defined as Sz(G)=∑_{e=uv ∈ E}n_u(e)n_v(e) where n_u(e) and n_v(e) are, respectively, the number of vertices of G lying closer to vertex u than to vertex v and the number of vertices of G lying closer to vertex v than to vertex u. Hansen used the computer programm AutoGraphiX and made the following conjecture about the Szeged index and the Wiener index for a bipartite connected graph G with n ≥ 4 vertices and m ≥ n edges: Sz(G)-W(G) ≥ 4n-8. Moreover the bound is best possible as shown by the graph composed of a cycle on 4 vertices C₄ and a tree T on n-3 vertices sharing a single vertex. This paper is to give a confirmative proof to this conjecture.

Cited by

• The (revised) Szeged index and the Wiener index of a nonbipartite graph

Related

• The (revised) Szeged index and the Wiener index of a nonbipartite graph
• Wiener Index of Quadrangulation Graphs
• Some results on the Wiener index related to the Šoltés problem of graphs
• An upper bound on the Wiener Index of a k-connected graph
• Wiener index and graphs, almost half of whose vertices satisfy Šoltés property