论文标题
严格弦图的整数拉普拉斯特征值
Integer Laplacian eigenvalues of strictly chordal graphs
论文作者
论文摘要
在本文中，我们建立了图形的经典不变性与其整数Laplacian特征值之间的关系，重点介绍了弦图的子类，严格的和弦图，并指出如何有效地实现其计算。首先，我们审查有关一般图的结果，表明通用顶点的数量以及虚假和真双胞胎的程度提供整数拉普拉斯特征值及其多重性。之后，我们证明严格弦图的许多整数laplacian特征值与特定的简单顶点集直接相关，并且与图形的最小顶点分离器有关。
In this paper, we establish the relation between classic invariants of graphs and their integer Laplacian eigenvalues, focusing on a subclass of chordal graphs, the strictly chordal graphs, and pointing out how their computation can be efficiently implemented. Firstly we review results concerning general graphs showing that the number of universal vertices and the degree of false and true twins provide integer Laplacian eigenvalues and their multiplicities. Afterwards, we prove that many integer Laplacian eigenvalues of a strictly chordal graph are directly related to particular simplicial vertex sets and to the minimal vertex separators of the graph.
