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

From papers

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(Lk1(G))L^k(G)=L(L^{k-1}(G)) for k1k\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 k2k\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 k3k\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.

Progress summary

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

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.