Welcome to MathOverflow

Question

1

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

flag	asked Dec 11 2011 at 23:07 Shahrooz 962●1●2●13

	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 2011 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 2011 at 23:39

Chris Godsil · Accepted Answer · 2011-12-11 23:34:43Z UTC

6

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

answered Dec 11 2011 at 23:34

Chris Godsil
5,694●1●8●22

	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 2011 at 11:06
	What is $K(G)$? – Chris Godsil Dec 12 2011 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 2011 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 2011 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 2011 at 10:41

show 2 more comments

spectrum and degree sequence

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.