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 <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mi mathvariant="bold">A</m:mi> </m:math> {\bf{A}} of a graph <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mi>G</m:mi> </m:math> G , that is not a copy of any row of <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mi mathvariant="bold">A</m:mi> </m:math> {\bf{A}} . We present a new approach different from the methods used to date. By considering the change in the nullity of <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mi mathvariant="bold">A</m:mi> </m:math> {\bf{A}} on adding an arbitrary vertex to a base graph <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mi>G</m:mi> </m:math> G , we seek counter-examples to the conjecture. As a result, we determine a class <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mi class="MJX-tex-caligraphic" mathvariant="script">C</m:mi> </m:math> {\mathcal{C}} of graphs that could be potential counter-examples to the conjecture. We use eigenvector techniques to show that <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mi class="MJX-tex-caligraphic" mathvariant="script">C</m:mi> </m:math> {\mathcal{C}} is restricted to the intersection of a number of families of graphs with particular properties.