图的2-边覆盖与拉普拉斯谱

Laplacian Spectrum and 2-edges-covering

覆盖图是指对原图G进行边和顶点的变化新得到一个图H,且G和H之间保持同态的关系,若图G的每2条边对应图H中的一条边,就称图H是G的一个2-边覆盖图。本文将证明图G的拉普拉斯谱可由它的2-边覆盖图H的两个变化图的谱而得到。

A 2-edge-covering between G and H is a homomorphism from the vertices of G to the vertices of H so that each edge is covered twice and edges in H can be lifted back to edges in G.This paper show how to compute the Laplacian spectrum of G by computing the Laplacian spectrum of two smaller graphs.