“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 16505
School of Mathematics
  Title:   Spectral properties of cographs and P5-free graphs
  Author(s):  Ebrahim Ghorbani
  Status:   To Appear
  Journal: Linear Multilinear Algebra
  Supported by:  IPM
A cograph is a simple graph which contains no path on 4 vertices as an induced subgraph.Weconsider the eigenvalues of adjacency matrices of cographs and prove that a graph G is a cograph if and only if no induced subgraph of G has an eigenvalue in the interval ( − 1, 0). It is also shown that the multiplicity of any eigenvalue of a cograph G does not exceed the sum of multiplicities of 0 and −1 as eigenvalues of G. We introduce a partial order on the vertex set of graphs G in terms of inclusions among the open and closed neighbourhoods of vertices, and conjecture that the multiplicity of any eigenvalue of a cograph G except for 0,−1 does not exceed the maximum size of an antichain with respect to that partial order. In two extreme cases (in particular for threshold graphs), the conjecture is shown to be true. Finally, we prove that bipartite P5-free graphs have no eigenvalue in the intervals ( − 1/2, 0) and (0, 1/2).

Download TeX format
back to top
scroll left or right