3
$\begingroup$

The half-transitive graphs form a curious class of graphs with some kind of intermediate symmetry that is non-trivial to achieve. More precisely, a graph is half-transitive if its symmetry group is

  • transitive on vertices,
  • transitive on edges, but
  • not transitive on arcs (i.e. edges cannot be flipped by a symmetry).

Several such graphs are known to exist (the Holt graph is the smallest one).

I am curious about the spectral properties of such graphs, in particular, I would like to prove bounds on the multiplicity of the second-largest eigenvalue of the adjacency matrix. Ideally, I want the following:

Question: Can we prove that for every half-transitive graph $G$ of vertex-degree $d$ the multiplicity $\mu$ of the second-largest eigenvalue cannot be in the range $3,...,d$, that is, either $\mu\le 2$ or $\mu >d$.

I have only empirical evidence for this (checking the half-transitive graphs in the Mathematica library). And I am also okay with replacing the bound $\mu\le 2$ by $\mu\le \mu_0$ for some fixed but not too large $\mu_0$.

$\endgroup$

1 Answer 1

4
$\begingroup$

I was looking for some work on half-transitive graphs when I stumbled across this question, to which the answer is "No" (at least in the original form where you want to bound the multiplicity by 2).

Here is some SageMath code that will construct a 48-vertex graph, verify that it is vertex-, edge-, but not arc-transitive, and then produce its characteristic polynomial.

(Either cut-n-paste into your own SageMath notebook or into the online Sage Cell Server)

x=Graph("osaSTB?????????@_B??K?E?G@__B@??p??WOCc@?WO@@W?CDO?OCa?C@a??OT??CDG???_?g_A?Aa?G?CG_A?CAGP?PE@@CACBCC_Cb?OO_G_X?AOCHAG@C@GQC?a?PGQ?CGCOcO?E?@_F_?B?K?N??Ko?K?o?EE??WE??]?CG?Q?BK?Q?@_N??{????")
print([x.is_vertex_transitive(), x.is_edge_transitive(), x.is_arc_transitive()])
print(x.characteristic_polynomial().factor())

The characteristic polynomial of $X$ is $(x - 8) * (x - 4)^3 * (x + 4)^5 * x^{15} * (x^2 - 8)^{12}$, so the second eigenvalue is $4$ which has multiplicity $3$ not $2$.

There is another 48-vertex half-transitive graph that is cospectral to this, and so there are two examples.

(There are two more 48-vertex half-transitive graphs that are not cospectral to this, and whose characteristic polynomials do satisfy your condition.)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .