“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 15342
School of Mathematics
  Title:   Cographs: Eigenvalues and Dilworth number
  Author(s):  Ebrahim Ghorbani
  Status:   Published
  Journal: Discrete Math.
  Vol.:  342
  Year:  2019
  Pages:   2797-2803
  Supported by:  IPM
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
scroll left or right