Potential counter-examples to a conjecture on the column space of the adjacency matrix

Abstract

Attempts to resolve the Akbari-Cameron-Khosrovshahi-conjecture have so far focused on the rank of a matrix. The conjecture claims that there exists a nonzero (0, 1)-vector in the row space of a (0, 1)-adjacency matrix A{\bf{A}} of a graph GG, that is not a copy of any row of A{\bf{A}}. We present a new approach different from the methods used to date. By considering the change in the nullity of A{\bf{A}} on adding an arbitrary vertex to a base graph GG, we seek counter-examples to the conjecture. As a result, we determine a class C{\mathcal{C}} of graphs that could be potential counter-examples to the conjecture. We use eigenvector techniques to show that C{\mathcal{C}} is restricted to the intersection of a number of families of graphs with particular properties.

Keywords

• akbari-cameron-khosrovshahi-conjecture
• adjacency matrix
• singular graphs
• core vertex
• main eigenvalues
• 05c50
• 15a18