Cographs, Eigenvalues and More

Cographs, Eigenvalues and More

Acographisasimplegraphwhichcontainsnopathon4verticesasaninduced subgraph. We show that a graph G is a cograph if and only if no induced subgraph of G has an (adjacency) eigenvalue in the interval (−1,0). The vicinal preorder on the vertex set of graphs is defined in terms of inclusions among the open and closed 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 best possible. We give a new characterization of the family of cographs based on existence of a basis consistingofweight2vectorsfortheeigenspacesofeither 0 or−1 eigenvalues. This partially answers a question of G. F. Royle (2003).

Acographisasimplegraphwhichcontainsnopathon4verticesasaninduced subgraph. We show that a graph G is a cograph if and only if no induced subgraph of G has an (adjacency) eigenvalue in the interval (−1,0). The vicinal preorder on the vertex set of graphs is defined in terms of inclusions among the open and closed 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 best possible. We give a new characterization of the family of cographs based on existence of a basis consistingofweight2vectorsfortheeigenspacesofeither 0 or−1 eigenvalues. This partially answers a question of G. F. Royle (2003).