Cographs: Eigenvalues and Dilworth Number

Ebrahim Ghorbani

Published 2018-03-01Version 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 $\lambda\ne0,-1$, does not exceed the Dilworth number of $G$ and show that this bound is best possible. We give a new characterization of the family of cographs based on the existence of a basis consisting of weight 2 vectors for the eigenspace of either $0$ or $-1$ eigenvalues. This partially answers a question of G. F. Royle (2003).