Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
charateristic polynomial of graph; graph spectra; extended double cover of graph
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
Search
Partner of
