On 6-regular vertex-transitive graphs having 42 nodes

Question

In answering a recent Question about $6$-regular graphs with $42$ vertices, I commented that even the vertex-transitive cases afford a lot of choices. Three such graphs were proposed, and I left it as a challenge to the interested Reader to verify non-isomorphism.

My hint was to fix a vertex $v$ and count the number of edges incident only to the six neighbors of $v$. The three graphs gave respective counts of $9,15,6$ edges between such neighbors, proving them non-isomorphic. A fourth example can be adduced, that of a $6$-regular vertex-transitive bipartite graph, where obviously the number of edges between neighbors of any one vertex is zero.

My question is what are the possible counts of edges between neighbors in $6$-regular vertex-transitive graphs having $42$ nodes. All the examples described have counts that are multiples of three, which I speculate is a necessary but not sufficient condition.

---

I have some thoughts about attacking this problem which I'd like to share.

A nontrivial graph $G$ which is vertex transitive will have a nontrivial automorphism group $\mathscr G$. Often the study of $G$ can be illuminated by the study of $\mathscr G$, as we see in this recent arXiv.org paper (2016) by Jing Chen AND Binzhou Xia:

On Isomorphisms of Vertex-Transitive Graphs

Note $\mathscr G$ has at least a subgroup $\mathscr H$ generated by those automorphisms which map some fixed vertex $v$ to one of its neighbors. If $G$ is connected, then $G$ is $\mathscr H$-vertex-transitive since we can get from $v$ to any other vertex $u$ by a sequence of automorphisms in $\mathscr H$. There is a slightly subtle concept involved here, noting that an automorphism $h$ maps $v$ to one of its neighbors if and only if $h$ maps every $u\in G$ to one of its neighbors, so that every step in the sequence outlined can be taken by one of the generators of $\mathscr H$.

If $G$ is not connected, then the components of $G$ must be equal in size, and in order for $G$ to be $6$-regular, that size must be a proper divisor $d$ of $42$ which is at least $7$. In other words the sizes of nontrivial components are tightly restricted, and we hope these possibilities can be quickly exhausted.

Update: In checking the known vertex transitive connected graphs of regular degree $6$, I found examples with $21$ nodes where the neighbors of a fixed vertex share a number of edges not divisible by $3$ (namely $4$ or $7$ edges are shared).

Answer 1

Apologies for the roughness of this post, but it overstayed its welcome in the Sandbox! It remains unresolved whether the neighbors of any vertex in a connected (single component) $6$-regular $42$-vertex simple graph will share only a number of edges divisible by three.

Disconnected Cases

As noted in the Question, disconnected examples will amount to vertex transitive 6-regular graphs on $v$ nodes where $v\gt 1$ is a divisor of $42$. Thus $v=7,14,21$ are possibilities, and small enough that all have been exhaustively cataloged by McKay and Royle.

The files there are (Unix) ASCII format/gzipped. However after extracting the files, one needs a utility showg to convert them to human-readable form.

Case $v=7$

The only $6$-regular graph on $7$ vertices is the complete one, $K_7$. This clique achieves $\binom{6}{2}=15$ edges among the six neighbors $N$ of any fixed vertex, and thus the maximum count of such edges in the "open neighborhood" of a vertex.

Figure 1: Complete graph on seven vertices

Case $v=14$

Among the $51$ vertex transitive connected graphs on $14$ vertices, there are eight which are $6$-regular. Of these, one has no edges between neighbors of $v$, two have $3$ edges there, four have $6$ such edges, and one has $9$.

The graph with no edges between neighbors of a vertex is bipartite, indeed the complete bipartite $K_{7,7}$ minus a $1$-factor (matching).

Case $v=21$

Among the $235$ vertex transitive connected graphs on $21$ vertices, there are twenty-eight which are $6$-regular. Of these, some have a number of edges between neighbors of $v$ which is not a multiple of three. Here's a tabulation of how many of these graphs have the given number of edges $e_{N}$ in the open neighborhood $N$ of a vertex:

$$ \begin{array}{c|c} e_{N} & \# \text{ of graphs} \\ \hline 0 & 4 \\ 1 & 3 \\ 2 & 1 \\ 3 & 8 \\ 4 & 3 \\ 5 & 2 \\ 6 & 4 \\ 7 & 2 \\ 8 & 0 \\ 9 & 1 \\ \hline \text{all} & 28 \end{array} $$

The showg output for the unique $6$-regular vertex transitive graph on $21$ nodes with $e_N = 2$ is as follows (nodes labelled $0$ to $20$):

Graph 17, order 21.
  0 : 1 2 3 4 5 6;
  1 : 0 3 7 9 14 17;
  2 : 0 4 8 10 14 18;
  3 : 0 1 8 10 13 20;
  4 : 0 2 7 9 12 19;
  5 : 0 8 10 11 12 15;
  6 : 0 7 9 11 13 16;
  7 : 1 4 6 8 16 17;
  8 : 2 3 5 7 15 18;
  9 : 1 4 6 11 12 15;
 10 : 2 3 5 11 13 16;
 11 : 5 6 9 10 19 20;
 12 : 4 5 9 14 18 20;
 13 : 3 6 10 14 17 19;
 14 : 1 2 12 13 19 20;
 15 : 5 8 9 16 17 20;
 16 : 6 7 10 15 18 19;
 17 : 1 7 13 15 18 20;
 18 : 2 8 12 16 17 19;
 19 : 4 11 13 14 16 18;
 20 : 3 11 12 14 15 17;