Geodesic
Spectra of extended double cover graphs
Czechoslovak Mathematical Journal, Tome 54 (2004) no. 4, pp. 1077-1082
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
Classification : 05C30, 05C50
Keywords: charateristic polynomial of graph; graph spectra; extended double cover of graph 
@article{CMJ_2004_54_4_a19,
     author = {Chen, Zhibo},
     title = {Spectra of extended double cover graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {1077--1082},
     year = {2004},
     volume = {54},
     number = {4},
     mrnumber = {2100015},
     zbl = {1080.05516},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_2004_54_4_a19/}
}
TY  - JOUR
AU  - Chen, Zhibo
TI  - Spectra of extended double cover graphs
JO  - Czechoslovak Mathematical Journal
PY  - 2004
SP  - 1077
EP  - 1082
VL  - 54
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/CMJ_2004_54_4_a19/
LA  - en
ID  - CMJ_2004_54_4_a19
ER  - 
%0 Journal Article
%A Chen, Zhibo
%T Spectra of extended double cover graphs
%J Czechoslovak Mathematical Journal
%D 2004
%P 1077-1082
%V 54
%N 4
%U http://geodesic.mathdoc.fr/item/CMJ_2004_54_4_a19/
%G en
%F CMJ_2004_54_4_a19
Chen, Zhibo. Spectra of extended double cover graphs. Czechoslovak Mathematical Journal, Tome 54 (2004) no. 4, pp. 1077-1082. http://geodesic.mathdoc.fr/item/CMJ_2004_54_4_a19/

[1] N. Alon: Eigenvalues and expanders. Combinatorica 6 (1986), 83–96. | DOI | MR | Zbl

[2] N. Biggs: Algebraic Graph Theory. Cambridge Univ. Press, Cambridge, 1974, 1993. | MR

[3] J. A. Bondy and U. S. R. Murty: Graph Theory with Applications. North-Holland, New York, 1979. | MR

[4] F. R. K. Chung: Spectral Graph Theory. Amer. Math. Soc., Rhode Island, 1997. | MR | Zbl

[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

[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

[7] D. M. Cvetković, P. Rowlinson and S. Simić: Eigenspaces of Graphs. Cambridge Univ. Press, Cambridge, 1997. | MR

[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 | MR | Zbl

[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

[11] F. Zhang and Z. Chen: Ordering graphs with small index and its application. Discrete Appl. Math 121 (2002), 295–306. | DOI | MR