“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
| Paper IPM / M / 15342 |
|
| Abstract: | |
|
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 de ned 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 6= 0;�???1, does not
exceed the Dilworth number of G and show that this bound is tight. G. F. Royle [The rank
of a cograph, Electron. J. Combin. 10 (2003), Note 11] proved that if a cograph G has no
pair of vertices with the same neighborhood, then G has no 0 eigenvalue, and asked if beside
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.
Download TeX format |
|
| back to top | |
