“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
| Paper IPM / M / 16505 |
|
| Abstract: | |
|
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 | |
