The overgraphs of generalized cospectral controllable graphs

Abstract

Two graphs are said to be generalized cospectral if they have the same charac- teristic polynomials and so do their complements. A graph is 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 G0 and H0 starting from a pair of generalized cospectral, non-isomorphic, controllable graphs G and H. We show that if G0 and H0 are controllable, then they are non-isomorphic.