An eigenvalue upper bound for 1-walk-regular graphs

Question

Let $G$ be a graph and suppose that $G$ is 1-walk-regular (or, if you prefer, vertex- and edge-transitive, or distance-regular). Let $\theta_1>\theta_2>\cdots>\theta_m$ be the distinct eigenvalues of its adjacency matrix. It is known that $\theta_1=\deg(G)$ (the vertex-degree of $G$).

Now, I believe that the following holds:

$$\theta_2 < \mathrm{deg}(G)\cdot\cos\Big(\frac{\pi}{2\mathrm{diam}(G)}\Big),$$

where $\mathrm{diam}(G)$ denotes the diameter of $G$. This bound can be quite off. However, if $G$ is antipodal (that is, for every vertex there is a unique maximally distant vertex), then I believe we even have

$$\theta_2 \le \mathrm{deg}(G)\cdot\cos\Big(\frac{\pi}{\mathrm{diam}(G)}\Big),$$

and this bound is actually attained with equality in many cases.

Question:

• Are these bounds known (or are there counterexamples)?
• Is known for which graphs the second inequality is satisfied with equality?

---

Update

As requested in the comments, I provide a list of some graphs that attain the second bound. Because I am most familiar with polytope theory, all my examples are skeleta of polytopes. The list includes the skeleton of ...

• an even-sided polygon (the edge-graph is the even cycle),
• a cross-polytopes (the edge-graph is the completement of a disjoint union of edges; these are the only antipodal graphs of diameter 2),
• the cuboctahedron (degree 4, diameter 3, $\theta_2=2$),
• the icosidodecahedron (degree 4, diameter 5, $\theta_2=1+\sqrt 5$),
• the 24-cell (degree 8, diameter 3, $\theta_2=4$),
• the 600-cell (degree 12, diameter 5, $\theta_2=3(1+\sqrt 5)$).
• ...

I think I have an understanding for why it works with these polytopes, and there are more of these in higher dimensions. In the light of these examples (and my idea of why they work) I wonder whether there is a graph that attains the bound and is

• not the edge-graph of a polytope, or
• not vertex/edge-transitive, or
• not of even degree.

Note that the bound can also be arbitrarily bad. E.g., numerical experiments suggest that the bound becomes worse for the crown graphs with increasing degree.

---

Update 2

I will explain how the second inequality is motivated and might be proved.

I consider a spectral embedding of the graph to the eigenvalue $\theta_2$. Because the graphs is 1-walk-regular, all its vertices are embedded on a sphere (of, say, radius $r=1$), and all edges will be embedded with the same length, say $\ell$. Without going into the details, this length can be expressed as

$$(*)\quad \ell=\sqrt{1-\frac{\theta_2}{\mathrm{deg}(G)}}.$$

Now I assumed (but I have not proof for this, see this qestion) that antipodal vertices are embedded "opposite to each other", that is, if $i,j\in V(G)$ are antipodal, then their embeddings satisfy $v_i=-v_j$.

Now, if there is a path of length $\mathrm{diam}(G)$ from $i$ to $j$, all vertices on the sphere, all edges of the same length, one can determine a lower bound on the length of these edges so that this path is possible. One can imagine how trigonometry enter the picture here. This lower bound on the edge length translated to an upper bound on the eigenvalue $\theta_2$ via $(*)$.

With this approximate reasoning I can explain how I came to the examples I know of. Compare the image of the cube and the cuboctahedron below:

In the cuboctahedron, the path connecting antipodal vertices is "flat", while in the cube it is not. That is, in the cuboctahedron the edges are as short as possible for reaching from one end of the circumsphere to the other in only $\mathrm{diam}(G)=3$ steps.

Here are some consequences for graphs that attain the bound:

• the spectral embedding of the graph to $\theta_2$ must decompose into embeddings of flat cycles of length $2\mathrm{diam}(G)$.
• the degree must be even as every flat cycle entering a vertex must leave the vertex in the opposite direction.

In the case of vertex- and edge-transitive polytopes this might allow the following characterization:

The edge-graph attains the bound, if and only if the vertex-figure is centrally symmetric.

More vague, for vertex- and edge-transitive graphs $G$ a characterization might be the following:

$G$ attains the bound if and only if the stabilizer $\Gamma_i\subseteq\mathrm{Aut}(G)$ at a vertex $i\in V$ induces a centrally symmetric symmetry on the neighborhood $N(i)$, whatever this means exactly.

It amazes me that up to that point all the examples I know of have been polytopal. I see no reason for why this should be the case.

Answer 1

Here is the graph as requested from the comments.

Take the cuboctahedron and then assign colours to the edges as follows:

There are 8 triangles and 6 quadrilaterals in this graph, and it takes a moment to confirm that each triangle has a unique red edge, and each quadrilateral has either one or three red edges. In particular, all faces have an odd number of red edges.

Now form a double cover by replacing each vertex $v$ by a pair of non-adjacent vertices $v$, $v'.$ If $vw$ is a black edge of the cuboctahedron, then add a matching $\{vw, v'w'\}$ (i.e., a "straight" matching) and if it is a red edges of the cuboctahedron, then add a matching $\{vw', v'w\}$ (i.e., a "crossed" matching).

(Of course, this can all be expressed as a "voltage graph" over $\mathbb{Z}_2$, where the black edges correspond to $0$ and the red edges to $1$.)

Anyway, this removes all the triangles and quadrilaterals, and so the resulting graph has diameter 3, girth 5, and characteristic polynomial $$ (x - 4) \cdot x^{3} \cdot (x + 2)^{5} \cdot (x - 2)^{7} \cdot (x^{2} + 2x - 2)^{4}. $$

It is not antipodal.