Spectra of extended double cover graphs

Zhibo Chen

Czechoslovak Mathematical Journal (2004)

  • Volume: 54, Issue: 4, page 1077-1082
  • ISSN: 0011-4642

Abstract

top
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 n th iterared double cover are also presented.

How to cite

top

Chen, Zhibo. "Spectra of extended double cover graphs." Czechoslovak Mathematical Journal 54.4 (2004): 1077-1082. <http://eudml.org/doc/30922>.

@article{Chen2004,
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 = \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.},
author = {Chen, Zhibo},
journal = {Czechoslovak Mathematical Journal},
keywords = {charateristic polynomial of graph; graph spectra; extended double cover of graph; charateristic polynomial of graph; graph spectra; extended double cover of graph},
language = {eng},
number = {4},
pages = {1077-1082},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Spectra of extended double cover graphs},
url = {http://eudml.org/doc/30922},
volume = {54},
year = {2004},
}

TY - JOUR
AU - Chen, Zhibo
TI - Spectra of extended double cover graphs
JO - Czechoslovak Mathematical Journal
PY - 2004
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 54
IS - 4
SP - 1077
EP - 1082
AB - 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.
LA - eng
KW - charateristic polynomial of graph; graph spectra; extended double cover of graph; charateristic polynomial of graph; graph spectra; extended double cover of graph
UR - http://eudml.org/doc/30922
ER -

References

top
  1. 10.1007/BF02579166, Combinatorica 6 (1986), 83–96. (1986) Zbl0661.05053MR0875835DOI10.1007/BF02579166
  2. Algebraic Graph Theory, Cambridge Univ. Press, Cambridge, 1974, 1993. (1974, 1993) MR1271140
  3. Graph Theory with Applications, North-Holland, New York, 1979. (1979) MR0538028
  4. Spectral Graph Theory, Amer. Math. Soc., Rhode Island, 1997. (1997) Zbl0867.05046MR1421568
  5. Recent Results in the Theory of Graph Spectra, North-Holand, New York, 1987. (1987) MR0926481
  6. Spectra of Graphs, Academic Press, New York, 1980; third edition: Johann Ambrosius Barth Verlag, 1995. (1980; third edition: Johann Ambrosius Barth Verlag, 1995) MR0572262
  7. Eigenspaces of Graphs, Cambridge Univ. Press, Cambridge, 1997. (1997) MR1440854
  8. Theory of matrices, Vol.  I, Chelsea, New York, 1960. (1960) 
  9. 10.1016/0166-218X(96)85159-6, Discrete Appl. Math. 67 (1996), 209–219. (1996) Zbl0851.05076MR1393305DOI10.1016/0166-218X(96)85159-6
  10. 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. (1974) MR0387126
  11. 10.1016/S0166-218X(01)00302-X, Discrete Appl. Math 121 (2002), 295–306. (2002) MR1907562DOI10.1016/S0166-218X(01)00302-X

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.