charateristic polynomial of graph; graph spectra; extended double cover of graph
The construction of the extended double cover was introduced by N. Alon  in 1986. For a simple graph $G$ with vertex set $V = \lbrace v_1,v_2, \dots , v_n \rbrace $, the extended double cover of $G$, denoted $G^*$, is the bipartite graph with bipartition $(X,Y)$ where $X = \lbrace x_1, x_2, \dots ,x_n \rbrace $ and $ Y = \lbrace y_1, y_2, \cdots ,y_n \rbrace $, in which $x_i$ and $y_j$ are adjacent iff $i=j$ or $v_i$ and $v_j$ are adjacent in $G$. In this paper we obtain formulas for the characteristic polynomial and the spectrum of $G^*$ in terms of the corresponding information of $G$. Three formulas are derived for the number of spanning trees in $G^*$ for a connected regular graph $G$. We show that while the extended double covers of cospectral graphs are cospectral, the converse does not hold. Some results on the spectra of the $n$th iterared double cover are also presented.
 N. Biggs: Algebraic Graph Theory
. Cambridge Univ. Press, Cambridge, 1974, 1993. MR 1271140
 J. A. Bondy and U. S. R. Murty: Graph Theory with Applications
. North-Holland, New York, 1979. MR 0538028
 D. M. Cvetković, M. Doob, I. Gutman and A. Torgasev: Recent Results in the Theory of Graph Spectra
. North-Holand, New York, 1987. MR 0926481
 D. M. Cvetković, M. Doob and H. Sachs: Spectra of Graphs
. Academic Press, New York, 1980; third edition: Johann Ambrosius Barth Verlag, 1995. MR 0572262
 D. M. Cvetković, P. Rowlinson and S. Simić: Eigenspaces of Graphs
. Cambridge Univ. Press, Cambridge, 1997. MR 1440854
 F. R. Grantmacher: Theory of matrices, Vol. I. Chelsea, New York, 1960.
 A. J. Schwenk: Computing the charateristic polynomial of a graph
. In: Graphs and Combinatorics. Lecture Notes in Mathematics Vol. 406, R. Bari, F. Harary (eds.), Springer-Verlag, New York, 1974, pp. 153–172. MR 0387126