3
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ A handy compendium of information about $k$-regular connected graphs for small $k$ is Markus Meringer's site Regular Graphs. However I did not see there indications of which graphs are vertex transitive. $\endgroup$ – hardmath Jul 10 '16 at 16:40
  • $\begingroup$ Vertex transitive graphs up to 31 nodes have been compiled by Brendan McKay and Gordan Royle (checked for completeness up through 26 nodes). $\endgroup$ – hardmath Jul 11 '16 at 0:18
  • 1
    $\begingroup$ Note that all vertex-transitive graphs of order up to 47 are now available (see arxiv.org/abs/1811.09015) so the answer is just a computation away. (You can probably e-mail Gordon Royle for the list of graphs.) $\endgroup$ – verret Jan 17 at 1:03
0
$\begingroup$

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.

Complete graph on seven vertices

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;
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.