The maximum order of adjacency matrices with a given rank

Research output: Contribution to journalArticleScientificpeer-review


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.
Original languageEnglish
Pages (from-to)223-232
JournalDesigns Codes and Cryptography
Issue number3
Publication statusPublished - 2012


Cite this