|Title:||Vertex types in threshold and chain graphs||Journal:||Discrete Applied Mathematics||Volume:||269||First page:||159||Last page:||168||Issue Date:||30-Sep-2019||Rank:||M22||ISSN:||0166-218X||DOI:||10.1016/j.dam.2019.02.040||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.
|Keywords:||Adjacency spectrum | Chain graphs | Threshold graphs | Vertex types||Publisher:||Elsevier||Project:||IPM, Grant No. 96050211
Graph theory and mathematical programming with applications in chemistry and computer science
Show full item record
checked on May 20, 2022
checked on Apr 8, 2022
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.