Spectra of Extended Double Cover Graphs |
| |
Authors: | Email author" target="_blank">Zhibo?ChenEmail author |
| |
Institution: | (1) Department of Mathematics, Penn State University, McKeesport, PA, 15132, U.S.A. |
| |
Abstract: | The construction of the extended double cover was introduced by N. Alon 1] in 1986. For a simple graph G with vertex set V = {v
1, v
2, ..., v
n
}, the extended double cover of G, denoted G
*, is the bipartite graph with bipartition (X, Y) where X = {x
1, x
2, ..., x
n
} and Y = {y
1, y
2, ..., y
n
}, 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 nth iterared double cover are also presented. |
| |
Keywords: | charateristic polynomial of graph graph spectra extended double cover of graph |
本文献已被 SpringerLink 等数据库收录! |
|