Cographs: Eigenvalues and Dilworth number
Cographs: Eigenvalues and Dilworth number
复制标题
Cographs：特征值和 Dilworth 数
DOI：
10.1016/j.disc.2018.09.016
复制
发表时间：
2018
影响因子：
0.8
通讯作者：
Ghorbani, Ebrahim
中科院分区：
文献类型：
--
作者：
Ghorbani, Ebrahim
上图是指在4个顶点上不含路的简单图作为导出子图。图的顶点集上的邻位预序是根据顶点邻域之间的包含关系定义的。图G中覆盖顶点集所需的关于邻位预序的最小链数称为图G的Dilworth数。我们证明了对任何上图G，任何特征值λ <$0，− 1的重数不超过G的Dilworth数，并证明了这个界是紧的。Royle（2003）证明了如果一个上图G不存在具有相同邻域的顶点对，则G不存在0特征值，并询问了除了上图之外，是否还有其他自然类的图也具有这一性质。我们给出了这个问题的部分答案，证明了一个H-自由图族具有此属性的充要条件是它是上图族的一个子类。对于-1本征值也有类似的结果。
A cograph is a simple graph which contains no path on 4 vertices as an induced subgraph. The vicinal preorder on the vertex set of a graph is defined in terms of inclusions among the neighborhoods of vertices. The minimum number of chains with respect to the vicinal preorder required to cover the vertex set of a graph G is called the Dilworth number of G. We prove that for any cograph G, the multiplicity of any eigenvalue λ≠ 0,− 1, does not exceed the Dilworth number of G and show that this bound is tight. Royle (2003) proved that if a cograph G has no pair of vertices with the same neighborhood, then G has no 0 eigenvalue, and asked if besides cographs, there are any other natural classes of graphs for which this property holds. We give a partial answer to this question by showing that an H-free family of graphs has this property if and only if it is a subclass of the family of cographs. A similar result is also shown to hold for the− 1 eigenvalue.
登录
查看更多内容
图中的主导子图具有一些禁止结构
影响因子：
0.8
作者：
Jiping Liu;H. Zhou
通讯作者：
H. Zhou
DOI：
--
发表时间：
1979
期刊：
影响因子：
--
作者：
F. Harary
通讯作者：
F. Harary
Cographs 和 P5-free 图谱的光谱特性
DOI：
--
发表时间：
2016
期刊：
影响因子：
--
作者：
E. Ghorbani
通讯作者：
E. Ghorbani
图的迪尔沃斯数
DOI：
--
发表时间：
1978
期刊：
影响因子：
--
作者：
S. Foldes;P. Hammer
通讯作者：
P. Hammer
影响因子：
1.1
作者：
Liang-Hao Huang;B. Tam;Shu-hui Wu
通讯作者：
Liang-Hao Huang;B. Tam;Shu-hui Wu