Hansen's Szeged–Wiener index conjecture for bipartite graphs

About 15 years old · traced to

Let GG be a finite, simple, connected bipartite graph with n≥4n \geq 4 vertices and m≥nm \geq n edges. Its Wiener index is

W(G)=∑{u,v}⊆V(G)d(u,v),W(G)=\sum_{\{u,v\}\subseteq V(G)}d(u,v),

and its Szeged index is

Sz(G)=∑e=uv∈E(G)nu(e)nv(e),Sz(G)=\sum_{e=uv\in E(G)}n_u(e)n_v(e),

where nu(e)n_u(e) and nv(e)n_v(e) count the vertices closer to uu and vv, respectively, for the edge e=uve=uv. Hansen's conjecture.

Sz(G)−W(G)≥4n−8.Sz(G)-W(G)\geq 4n-8.

The bound is best possible: equality is attained by a graph formed from a 44-cycle C4C_4 and a tree TT on n−3n-3 vertices sharing one vertex. The conjecture concerns a lower bound relating two classical graph indices and, in the stated source, no resolution is supplied.

References

Primary source

Lily Chen, Xueliang Li and Mengmeng Liu, “On a relation between the Szeged index and the Wiener index for bipartite graphs”, arXiv:1210.6460 (2012).

Additional references

2 papers in this index state this conjecture (2011–2012). The statement above is taken from the most recent of them; the others are arXiv:1104.2122.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.