We look for the maximum order m(r) of the adjacency matrix A of a graph G with a fixed rank r, provided A has no repeated rows or all-zero row. Akbari, Cameron and Khosrovshahi conjecture that m(r) = 2(r+2)/2 − 2 if r is even, and m(r) = 5 · 2(r−3)/2 − 2 if r is odd. We prove the conjecture and characterize G in the case that G contains an induced subgraph (r/2) · K2 or (r−3/2) · K2 + K3.
|Journal||Designs Codes and Cryptography|
|Publication status||Published - 2012|