### Abstract

*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 |

### Fingerprint

### Cite this

}

*Designs Codes and Cryptography*, vol. 65, no. 3, pp. 223-232.

**The maximum order of adjacency matrices with a given rank.** / Haemers, W.H.; Peeters, M.J.P.

Research output: Contribution to journal › Article › Scientific › peer-review

TY - JOUR

T1 - The maximum order of adjacency matrices with a given rank

AU - Haemers, W.H.

AU - Peeters, M.J.P.

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

M3 - Article

VL - 65

SP - 223

EP - 232

JO - Designs, Codes and Cryptography

JF - Designs, Codes and Cryptography

SN - 0925-1022

IS - 3

ER -