On simply structured kernel bases of unicyclic graphs (Q2469301)

This paper is dedicated to the study of unicyclic graphs for which there exists a simply structured kernel basis. Let \(G=(V,E)\) be a connected graph and \(A(G)\) its adjacency matrix. The authors refer to the kernel of the adjacency matrix of a graph as the kernel of the graph. A basis of a real vector space is called simply structured if it consists only of vectors with entries in \(\{-1,0,1 \}\). Of course, not every unicyclic graph has a simply structured kernel basis, but this is different from the situation for trees. The authors are interested in identifying exactly those unicyclic graphs which admit a simply structured kernel basis. The main result of the paper has the following form. Let \(G\) be a unicyclic graph with cycle \(C\) and let \(T_i\) be the trees emanating from \(C\). Assume that each tree \(T_i\) is attached to \(C\) by an edge \(v_iu_i\) such that \(u_i\) and \(v_i\) are vertices of \(C\) and \(T_i\), respectively. Then \(G\) has a simply structured kernel basis unless \(| C| \equiv 2\mod4\) and a particular condition holds. The authors present three different conditions, allowing to state an algorithmic, an algebraic and a structural characterization of the unicyclic graphs with simply structured kernel bases.