Conjecture on the construction code maximizing Kemeny's constant for threshold graphs

Let GG be a threshold graph of order nn, represented by a construction code, and let K(G)\mathcal{K}(G) denote its Kemeny constant. Maximizing construction-code conjecture. The threshold graph of order nn with maximum Kemeny's constant has construction code of the form 0111..1100000...00010111..1100000...0001. This conjecture has been confirmed computationally for all threshold graphs of orders up to n=30n=30, but the asserted form is not established in general.

Sources & referencesView supporting material

Primary source

Jane Breen, Sooyeong Kim, Alexander Low Fung, Amy Mann, Andrei A. Parfeni and Giovanni Tedesco, “Threshold graphs, Kemeny's constant, and related random walk parameters”, arXiv:2310.08552 (2023).

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.