Abstract
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 language | English |
---|---|
Pages (from-to) | 223-232 |
Journal | Designs Codes and Cryptography |
Volume | 65 |
Issue number | 3 |
Publication status | Published - 2012 |