Hriňáková–Knor–Škrekovski conjecture on extremal iterated-line-graph Wiener ratios

About 2 years old · traced to

Let GG be a graph on nn vertices. The Wiener index W(G)W(G) is the sum of distances over all unordered pairs of vertices. Let L(G)L(G) be the line graph of GG, define L0(G)=GL^0(G)=G and Lk(G)=L(Lk−1(G))L^k(G)=L(L^{k-1}(G)) for k≥1k\geq 1, and set

Rk(G)=W(Lk(G))W(G).R_k(G)=\frac{W(L^k(G))}{W(G)}.

Hriňáková–Knor–Škrekovski conjecture. For large nn and k≥2k\geq 2, among all graphs GG on nn vertices, Rk(G)R_k(G) attains its maximum at G=KnG=K_n and its minimum at G=PnG=P_n.

The minimum for k=1k=1 is known to be attained by the star, while for trees and k≥3k\geq 3 the path is known to attain the minimum. The conjecture concerns the remaining extremal cases and the simultaneous maximum and minimum over all graphs.

References

Primary source

Mohammad Ghebleh and Ali Kanso, “On the Second-Order Wiener Ratios of Iterated Line Graphs”, arXiv:2401.12370 (2024).

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.