2018/03/01 by Milica Anđelić, M. Anđelić, Anđelić, M. +6
Mathematics · #05C50 #Algebraic structures and combinatorial models #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Graph theory and applications #math.CO #msc:05C50
paper · pdf · doi:10.48550/arxiv.1803.00245
arxiv created 2018/03/01 · openalex publication_date 2018/03/01 · arxiv updated 2018/03/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A graph is called a chain graph if it is bipartite and the neighborhoods of the vertices in each color 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 color 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 \em et al.