“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 dened 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 Hfree 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 