Vertex types in threshold and chain graphs

Abstract

A graph is called a chain graph if it is bipartite and the neighbourhoods of the vertices in each colour class form a chain with respect to inclusion. A threshold graph can be obtained from a chain graph by making adjacent all pairs of vertices in one colour class. Given a graph G, let λ be an eigenvalue (of the adjacency matrix) of G with multiplicity k≥1. A vertex v of G is a downer, or neutral, or Parter depending whether the multiplicity of λ in G−v is k−1, or k, or k+1, respectively. We consider vertex types in the above sense in threshold and chain graphs. In particular, we show that chain graphs can have neutral vertices, disproving a conjecture by Alazemi et al.