We have the spectrum and the degree sequence of one graph. Can we uniquely determine the graph with these given information?
$\begingroup$
$\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$– Gjergji ZaimiCommented 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$– Chris GodsilCommented Dec 11, 2011 at 23:39
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
7
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
-
$\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$– ShahroozCommented Dec 12, 2011 at 11:06
-
-
$\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$– ShahroozCommented 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$ Commented 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$– ShahroozCommented Dec 13, 2011 at 10:41