Spectra of extended double cover graphs

Title:

Spectra of extended double cover graphs

Creator:

Chen, Zhibo

Identifier:

https://cdk.lib.cas.cz/client/handle/uuid:871b8e62-ffc2-48b0-9a16-5c2b8fc000ef
uuid:871b8e62-ffc2-48b0-9a16-5c2b8fc000ef

Subject:

characteristic polynomial of graph, graph spectra, and extended double cover of graph

Type:

model:article and TEXT

Format:

bez média and svazek

Description:

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.

Language:

English

Rights:

http://creativecommons.org/publicdomain/mark/1.0/
policy:public

Coverage:

1077-1082

Source:

Czechoslovak Mathematical Journal | 2004 Volume:54 | Number:4

Harvested from:

CDK

Metadata only:

false