Nordhaus–Gaddum-type theorem for Wiener index of graphs when decomposing into three parts

Let KnKn be the complete graph of order nn. Assume that (G1,G2,G3)(G1,G2,G3) is a 33-decomposition of KnKn such that GiGi is connected for each i=1,2,3i=1,2,3. Then for any sufficiently large nn, 5n2≤∑i=13W(Gi)≤n3−n3+n2+2(n−1).We also prove that both bounds are best possible.

► We obtain sharp upper and lower bounds on the Wiener index of the decomposition of complete graphs into three parts. ► Our result extends the Nordhaus–Gaddum-type theorem on Wiener index. ► For given positive integers, dd and nn, we determine the graph with maximum Wiener index with order nn and Δ(G)≥dΔ(G)≥d.