The overgraphs of generalized cospectral controllable graphs (Q668064)

Summary: Two graphs are said to be \textit{generalized cospectral} if they have the same characteristic polynomials and so do their complements. A graph is \textit{controllable} if its walk matrix is nonsingular; equivalently, if all the eigenvalues of its adjacency matrix are simple and main. A graph \(H\) on \((n+1)\) vertices is an overgraph of another graph \(G\) on \(n\) vertices if \(G\) is a vertex-deleted subgraph of \(H\). We prove that no two distinct overgraphs of a controllable graph are generalized cospectral; this strengthens an earlier result that stated that no two such overgraphs are isomorphic. Moreover, we present methods that produce pairs of generalized cospectral graphs \(G'\) and \(H'\) starting from a pair of generalized cospectral, non-isomorphic, controllable graphs \(G\) and \(H\). We show that if \(G'\) and \(H'\) are controllable, then they are non-isomorphic.