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

We have the spectrum and the degree sequence of one graph. Can we uniquely determine the graph with these given information?

share|improve this question
    
Do you mean Laplacian spectrum or adjacency spectrum? In any case, most examples of cospectral pairs also have the same degree sequence. –  Gjergji Zaimi Dec 11 '11 at 23:27
    
I do not think it is true that in most examples of cospectral pairs the graphs have the same degree sequence. It's not true for small numbers of vertices, $(n\le 9 say?). I suspect that many do have the same degree sequence, but I've never seen a discussion of the matter. For larger $n$ your guess might be as good as mine. –  Chris Godsil Dec 11 '11 at 23:39

1 Answer 1

up vote 6 down vote accepted

No. One simple class of examples are Latin square graphs. If $L$ is an $n\times n$ Latin square with entries from $\{1,\ldots,n\}$, the vertices of Latin square graph are the $n^2$ triples; two triples are adjacent if the agree on one of their three coordinates. This is a regular graph of valency $3(n-1)$. In fact these graphs are strongly regular, and their eigenvalues are $3(n-1)$, $n$ and $-3$ with respective multiplicities 1, $n-3$ and $n^2-3n+2$. Two Latin squares give non-isomorphic graphs in they are in different main classes (see the wikipedia article) and there are many main classes for large $n$. When $n=4$ there are two, and over a quarter of a million when $n=8$.

You can find some of the theory on line at http://www.cs.yale.edu/homes/spielman/561/lect23-09.pdf

share|improve this answer
    
I think it is true if we know our graph has at least n(n-1)/K(G) edges, where V(G)=n and 2=<K(G)=<3 Thanks a lot. –  Shahrooz Dec 12 '11 at 11:06
    
What is $K(G)$? –  Chris Godsil Dec 12 '11 at 13:04
    
I defined K(G),K(G) is the set of numbers related to the graph G, that with some given information about G, uniquely determine the graph. In this case, if we have adjacency spectrum and degree sequence, if K(G) be a number in closed interval [2,3], or our graph have approximately n(n-1)/K(G) edges, the graph uniquely is determinable. I am finding the interval of K(G) with some probabilistic method. In general, we have the spectrum and the property P(G) of graphs G. I am finding the minimum number of edges, that force the graph be unique. –  Shahrooz Dec 13 '11 at 1:31
    
I still do not know what $K(G)$ is. But if $q$ is a prime power congruent to 1 mod 4, then there are conference graphs on $q$ vertices which are strongly regular with valency $(q-1)/2$. There are non-isomorphic conference graphs on 25 and 29 vertices (and infinitely many other orders, look for Peisert graphs. Conference graphs on the same number of vertices are cospectral. –  Chris Godsil Dec 13 '11 at 2:24
    
My conjecture is: If we have the spectrum of graph $G$ and this graph has approximately $|V(G)|(|V(G)|-1)/K(G)$ edges, where $K(G) in [2,3]$, this graph is uniquely determinable. for example, if $K(G)=2$, we have $G=K_n$ and the conjecture is true. Your previous example, Conference graph, has $q(q-1)/4$ edges and doesn't have the conditions of conjecture. Do you think this conjecture be true? –  Shahrooz Dec 13 '11 at 10:41

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.