Existence of a Non-Zero $(0,1)$-Vector in the Row Space of Adjacency Matrices of Simple Graphs

Abstract

We look for a non-zero $(0,1)$-vector in the row space of the adjacency matrix $A(\Gamma )$ of a graph $\Gamma ,$ provided $\Gamma$ has at least one edge. Akbari, Cameron, and Khosrovshahi conjectured that there exists a non-zero $(0,1)$-vector in the row space of $A(\Gamma )$ (over the real numbers) which does not occur as a row of $A(\Gamma ).$ This conjecture can be easily verified for graphs having diameter is equal to $1$ (complete graphs). In this article, we affirmatively prove this conjecture for any graph whose diameter is $\ge 4.$ Furthermore, in the remaining two cases that is, for graphs with diameter is equal to $2$ or $3,$ we report some progress in support of the conjecture.

15 pages, 7figures