Spectral properties of cographs and P5-free graphs
Spectral properties of cographs and P5-free graphs
复制标题
Cographs 和 P5-free 图谱的光谱特性
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
E. Ghorbani
中科院分区：
文献类型：
--
作者：
E. Ghorbani
摘要上图是一个简单图，它的导出子图是4个顶点上不含路的图。本文研究了上图的邻接矩阵的特征值，证明了图G是上图的充要条件是G的导出子图在区间内没有特征值。证明了上图G的任何特征值的重数不超过G的特征值0和的重数之和。我们在图G的顶点集上引入了一个偏序，它是关于顶点的开邻域和闭邻域之间的包含关系的，并猜想除的余图G的任何特征值的重数都不超过关于该偏序的反链的最大尺寸.在两个极端的情况下（特别是阈值图），该猜想是真实的。最后，我们证明了无二部图在区间和（0，1 / 2）内没有特征值.
ABSTRACT A cograph is a simple graph which contains no path on 4 vertices as an induced subgraph. We consider the eigenvalues of adjacency matrices of cographs and prove that a graph G is a cograph if and only if no induced subgraph of G has an eigenvalue in the interval . It is also shown that the multiplicity of any eigenvalue of a cograph G does not exceed the sum of multiplicities of 0 and as eigenvalues of G. We introduce a partial order on the vertex set of graphs G in terms of inclusions among the open and closed neighbourhoods of vertices, and conjecture that the multiplicity of any eigenvalue of a cograph G except for does not exceed the maximum size of an antichain with respect to that partial order. In two extreme cases (in particular for threshold graphs), the conjecture is shown to be true. Finally, we prove that bipartite -free graphs have no eigenvalue in the intervals and (0, 1 / 2).