The reduced-graph order conjecture of Akbari, Cameron, and Khosrovshahi

Let r2r\geq 2, 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 m(r)m(r) for

m(r)={2(r+2)/22if r is even,52(r3)/22if r is odd.m(r)=\begin{cases}2^{(r+2)/2}-2&\text{if }r\text{ is even},\\5\cdot2^{(r-3)/2}-2&\text{if }r\text{ is odd}. \end{cases}

Akbari–Cameron–Khosrovshahi conjecture. The order of any reduced graph of rank rr is at most m(r)m(r). 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

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.