Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
@ 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? –  Shahrooz Jan 2 '13 at 9:48
    
@Shahrooz: For what it's worth, my guess is that at most finitely many differences cannot be realized. –  Chris Godsil Jan 2 '13 at 11:08
    
@ 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? –  Shahrooz Jan 2 '13 at 15:34
    
@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. –  Chris Godsil Jan 4 '13 at 4:02
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.