The maximum order of adjacency matrices with a given rank

Research output: Contribution to journalArticleScientificpeer-review

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

Fingerprint

Adjacency Matrix
Induced Subgraph
Odd
Zero
Graph in graph theory

Cite this

@article{6b0678559e264a868157904dfbaced92,
title = "The maximum order of adjacency matrices with a given rank",
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.",
author = "W.H. Haemers and M.J.P. Peeters",
year = "2012",
language = "English",
volume = "65",
pages = "223--232",
journal = "Designs, Codes and Cryptography",
issn = "0925-1022",
publisher = "Springer Netherlands",
number = "3",

}

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

In: Designs Codes and Cryptography, Vol. 65, No. 3, 2012, p. 223-232.

Research output: Contribution to journalArticleScientificpeer-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 -