The largest-Laplacian-eigenvalue conjecture for Hamming graphs
Let be the Hamming graph on vertices, with two vertices adjacent when their Hamming distance is . Write
Largest-Laplacian-eigenvalue conjecture. If and , with even if , then is the largest Laplacian eigenvalue of . This conjecture identifies the Laplacian eigenvalue arising from the common Hamming-scheme idempotent as the extremal one in the stated parameter range, extending the known max-cut result for the relevant binary Hamming graphs. Its general status is not established in the supplied source.
References
Primary source
Edwin R. van Dam and Renata Sotirov, “New bounds for the max-k-cut and chromatic number of a graph”, arXiv:1503.06595 (2015).
Additional references
2 papers in this index state this conjecture (2013–2015). The statement above is taken from the most recent of them; the others are arXiv:1309.2163.
Progress summary
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.