# Article

Full entry | PDF   (0.2 MB)
Keywords:
charateristic polynomial of graph; graph spectra; extended double cover of graph
Summary:
The construction of the extended double cover was introduced by N. Alon [1] 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.
References:
[1] N. Alon: Eigenvalues and expanders. Combinatorica 6 (1986), 83–96. DOI 10.1007/BF02579166 | MR 0875835 | Zbl 0661.05053
[2] N. Biggs: Algebraic Graph Theory. Cambridge Univ. Press, Cambridge, 1974, 1993. MR 1271140
[3] J. A. Bondy and U. S. R. Murty: Graph Theory with Applications. North-Holland, New York, 1979. MR 0538028
[4] F. R. K. Chung: Spectral Graph Theory. Amer. Math. Soc., Rhode Island, 1997. MR 1421568 | Zbl 0867.05046
[5] 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
[6] 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
[7] D. M. Cvetković, P. Rowlinson and S. Simić: Eigenspaces of Graphs. Cambridge Univ. Press, Cambridge, 1997. MR 1440854
[8] F. R. Grantmacher: Theory of matrices, Vol.  I. Chelsea, New York, 1960.
[9] P. Rowlinson: The characteristic polynomials of modified graphs. Discrete Appl. Math. 67 (1996), 209–219. DOI 10.1016/0166-218X(96)85159-6 | MR 1393305 | Zbl 0851.05076
[10] 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
[11] F. Zhang and Z. Chen: Ordering graphs with small index and its application. Discrete Appl. Math 121 (2002), 295–306. DOI 10.1016/S0166-218X(01)00302-X | MR 1907562

Partner of