1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Do you mean Laplacian spectrum or adjacency spectrum? In any case, most examples of cospectral pairs also have the same degree sequence. $\endgroup$ Dec 11, 2011 at 23:27
  • $\begingroup$ 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. $\endgroup$ Dec 11, 2011 at 23:39

1 Answer 1

6
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – Shahrooz
    Dec 12, 2011 at 11:06
  • $\begingroup$ What is $K(G)$? $\endgroup$ Dec 12, 2011 at 13:04
  • $\begingroup$ 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. $\endgroup$
    – Shahrooz
    Dec 13, 2011 at 1:31
  • $\begingroup$ 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. $\endgroup$ Dec 13, 2011 at 2:24
  • $\begingroup$ 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? $\endgroup$
    – Shahrooz
    Dec 13, 2011 at 10:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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