Authors: Anđelić, Milica
Ghorbani, Ebrahim
Simić, Slobodan 
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
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 Jun 23, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.