The largest-Laplacian-eigenvalue conjecture for Hamming graphs
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.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.