| Title:
|
Spectra of extended double cover graphs (English) |
| Author:
|
Chen, Zhibo |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
54 |
| Issue:
|
4 |
| Year:
|
2004 |
| Pages:
|
1077-1082 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
charateristic polynomial of graph |
| Keyword:
|
graph spectra |
| Keyword:
|
extended double cover of graph |
| MSC:
|
05C30 |
| MSC:
|
05C50 |
| idZBL:
|
Zbl 1080.05516 |
| idMR:
|
MR2100015 |
| . |
| Date available:
|
2009-09-24T11:20:15Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/127952 |
| . |
| Reference:
|
[1] N. Alon: Eigenvalues and expanders.Combinatorica 6 (1986), 83–96. Zbl 0661.05053, MR 0875835, 10.1007/BF02579166 |
| Reference:
|
[2] N. Biggs: Algebraic Graph Theory.Cambridge Univ. Press, Cambridge, 1974, 1993. MR 1271140 |
| Reference:
|
[3] J. A. Bondy and U. S. R. Murty: Graph Theory with Applications.North-Holland, New York, 1979. MR 0538028 |
| Reference:
|
[4] F. R. K. Chung: Spectral Graph Theory.Amer. Math. Soc., Rhode Island, 1997. Zbl 0867.05046, MR 1421568 |
| Reference:
|
[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 |
| Reference:
|
[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 |
| Reference:
|
[7] D. M. Cvetković, P. Rowlinson and S. Simić: Eigenspaces of Graphs.Cambridge Univ. Press, Cambridge, 1997. MR 1440854 |
| Reference:
|
[8] F. R. Grantmacher: Theory of matrices, Vol. I.Chelsea, New York, 1960. |
| Reference:
|
[9] P. Rowlinson: The characteristic polynomials of modified graphs.Discrete Appl. Math. 67 (1996), 209–219. Zbl 0851.05076, MR 1393305, 10.1016/0166-218X(96)85159-6 |
| Reference:
|
[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 |
| Reference:
|
[11] F. Zhang and Z. Chen: Ordering graphs with small index and its application.Discrete Appl. Math 121 (2002), 295–306. MR 1907562, 10.1016/S0166-218X(01)00302-X |
| . |
