A graph is called vertex and edge transitive if the automorphism group is transitive on both vertices and edges.
The spectrum of a graph is the collection (with multiplicities) of eigenvalues of the incidence matrix.
Supposedly, it is conjectured that almost all graphs have the property that they are the unique graph with their spectrum (at least, according to MathWorld).
If $\Gamma_1,\Gamma_2$ are two vertex and edge transitive graphs, with the same valence, which are isospectral (have the same spectrum) then does it follow that $\Gamma_1\cong \Gamma_2$?
Best Answer
Actually a graph is called half-transitive if it is vertex and edge transitive, but not arc-transitive. I am going to assume here that the term means what you chose it to mean.
Van Dam and Koolen construct distance-regular graphs with the same parameters (and hence the same spectrum) as the Grassmann graphs. They show that their graphs are not vertex transitive. The Grassmann graphs are distance transitive, and hence both arc and edge transitive. (Remark: the vertices of the Grassmann graph $G_q(v,k)$ are the $k$-dimensional subspaces of a vector space of dimension $v$ over the field of order $q$, two subspaces are adjacent if their intersection has dimension $k-1$.) If you google on Van Dam and Koolen, you'll easily find their paper.
For a second class of examples, there is a family of arc-transitive self-complementary graphs due to Peisert, which are strongly regular with the same parameters as the Paley graphs.
I do not know of examples of cospectral graphs which are half-transitive in the usual sense of the term. I am confident that there will be such things, but none may be known.