1
$\begingroup$

There are some facts that can be found by the spectrum of adjacency matrix of graph.For example, the number of edges and vertices, is bipartite or not, is complete multipartite or not and so on. Can we say anything about the clique number of two cospectral graphs?

We can construct the graphs $G_1$ and $G_2$ that they are cospectral and for arbitrary $k\in N$, the difference of clique number of these two graphs be grater than $k$. But, as I know, these graphs are disconnected.

So, my question is in connected case. I mean, suppose $G_1$ and $G_2$ are cospectral and connected. What can we say about their clique numbers?

Thanks for any helpful answer.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

Let $X$ and $Y$ be two cospectral graphs with maximum clique size $a$ and $b$ respectively. Then their $k$-fold strong powers $X(k)$ and $Y(k)$ are cospectral and the maximum size of a clique is $a^k$ and $b^k$ respectively. (The cliques of maximum size in a strong product are strong products of maximum sized cliques in the factors.) Since the strong product of connected graphs is connected, we have our examples.

We could take $X$ and $Y$ to be the Shrikande graph ($a=3$) and the line graph of $K_{4,4}$ ($b=4$). There are smaller examples, but I am too lazy to look right now.

Improve this answer
$\endgroup$
4
  • $\begingroup$ @ Dear Godsil, thank you very much. In disconnected case, we can control the differences of the clique number. I mean, for any integer $k$, there are cospectral mate $G_1$ and $G_2$, where the difference of their clique number is $k$. I think in connected case, it is not true. Am I think in true way? $\endgroup$
    – Shahrooz
    Commented Jan 2, 2013 at 9:48
  • $\begingroup$ @Shahrooz: For what it's worth, my guess is that at most finitely many differences cannot be realized. $\endgroup$
    – Chris Godsil
    Commented Jan 2, 2013 at 11:08
  • $\begingroup$ @ Godsil: I think you are right.But just a view; Suppose $G$ has a clique with largest size and vertex set $W$. The graph spectrum is very sensitive to this induced subgraph. I mean, the connection set between $W$ and $V(G)-W$ are important in the parameter that affect to the spectrum. Also, let $t$ be the minimum number of complete subgraphs of $G$ that these subgraphs mutually do not share any edges (maybe share vertices) and their union is $G$. The parameter $t$ strongly depend to the spectrum of $G$. I think it is very hard to decide about this problem. Do you agree with me dear Godsil? $\endgroup$
    – Shahrooz
    Commented Jan 2, 2013 at 15:34
  • $\begingroup$ @Shahrooz: Your parameter $t$ is just the chromatic number of the complement. There are lower bounds on chromatic number in terms of eigenvalues. However I expect that cospectral non-bipartite graphs can differ considerably in chromatic number. $\endgroup$
    – Chris Godsil
    Commented Jan 4, 2013 at 4:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .