The overgraphs of generalized cospectral controllable graphs
The electronic journal of combinatorics, Tome 26 (2019) no. 1
Two graphs are said to be generalized cospectral if they have the same characteristic 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 $G^\prime$ and $H^\prime$ starting from a pair of generalized cospectral, non-isomorphic, controllable graphs $G$ and $H$. We show that if $G^\prime$ and $H^\prime$ are controllable, then they are non-isomorphic.
@article{10_37236_7883,
author = {Alexander Farrugia},
title = {The overgraphs of generalized cospectral controllable graphs},
journal = {The electronic journal of combinatorics},
year = {2019},
volume = {26},
number = {1},
doi = {10.37236/7883},
zbl = {1409.05129},
url = {http://geodesic.mathdoc.fr/articles/10.37236/7883/}
}
Alexander Farrugia. The overgraphs of generalized cospectral controllable graphs. The electronic journal of combinatorics, Tome 26 (2019) no. 1. doi: 10.37236/7883
Cité par Sources :