The reduced-graph order conjecture of Akbari, Cameron, and Khosrovshahi
The reduced-graph order conjecture of Akbari, Cameron, and Khosrovshahi
Let , and let a reduced graph mean a graph with no pair of vertices that can be removed without changing the relevant adjacency-matrix rank. Write for
Akbari–Cameron–Khosrovshahi conjecture. The order of any reduced graph of rank is at most . This conjecture is presented as a bound on the order of reduced graphs in terms of adjacency-matrix rank; the paper cites it as a proposal of Akbari, Cameron, and Khosrovshahi, without giving a resolution.
Sources & referencesView supporting material
Primary source
Saieed Akbari, Clive Elphick, Hitesh Kumar, Shivaramakrishna Pragada and Quanyu Tang, “A new conjecture on the inertia of graphs”, arXiv:2508.01163 (2025).
Additional references
3 papers in this index state this conjecture (2012–2025). The statement above is taken from the most recent of them; the others are arXiv:2103.13489, arXiv:1201.3060.
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.