This is a continuation of the post A table of small quartic graphs. As with that post, it’s modeled on the handy wikipedia page Table of simple cubic graphs.
According to SageMath computations, there are 1544 connected, 4-regular graphs. Exactly 2 of these are symmetric (ie, arc transitive), also vertex-transitive and edge-transitive. Exactly 8 of these are vertex-transitive but not edge-transitive. None are distance regular.
Example 1: The first example of such a symmetric graph is the circulant graph with parameters (12, [1,5]), depicted below. It is bipartite, has girth 4, and its automorphism group has order 768, being generated by 
Example 2: The second example of such a symmetric graph is the cuboctahedral graph, depicted below. It has girth 3, chromatic number 3, and its automorphism group has order 48, being generated by 
to be
be a harmonic morphism from a graph 
to a graph 
. Then![{\rm genus}(\Gamma_2)-1 = {\rm deg}(\phi)({\rm genus}(\Gamma_1)-1)+\sum_{x\in V_2} [m_\phi(x)+\frac{1}{2}\nu_\phi(x)-1].](https://s0.wp.com/latex.php?latex=%7B%5Crm+genus%7D%28%5CGamma_2%29-1+%3D+%7B%5Crm+deg%7D%28%5Cphi%29%28%7B%5Crm+genus%7D%28%5CGamma_1%29-1%29%2B%5Csum_%7Bx%5Cin+V_2%7D+%5Bm_%5Cphi%28x%29%2B%5Cfrac%7B1%7D%7B2%7D%5Cnu_%5Cphi%28x%29-1%5D.&bg=ffffff&fg=323232&s=0&c=20201002)
denotes the horizontal multiplicity and 
denotes the vertical multiplicity.
-regular and 
-regular.
be a non-trivial harmonic morphism from a connected 
.
is a harmonic morphism. Let 
be adjacent vertices of 
. Then either (a) 
and 
“collapses” the edge (vertical) 
or (b) 
and the vertices 
and 
are adjacent in 
. In the particular case of this post (ie, the case of 
the white vertex is not adjacent to the blue or red vertex, none of the harmonic colored graphs below can have a white vertex adjacent to a blue or red vertex.
as the domain in this post. However, before we get to examples (obtained by using 
be a harmonic morphism from a graph 
vertices to the path graph having 
vertices. Let 
be the coloring map (identified with an n-tuple whose coordinates are in 
). Associated to f is a partition ![\Pi_f=[n_0,\dots,n_{k-1}]](https://s0.wp.com/latex.php?latex=%5CPi_f%3D%5Bn_0%2C%5Cdots%2Cn_%7Bk-1%7D%5D&bg=ffffff&fg=323232&s=0&c=20201002)
of n (here ![[...]](https://s0.wp.com/latex.php?latex=%5B...%5D&bg=ffffff&fg=323232&s=0&c=20201002)
is a multi-set, so repetition is allowed but the ordering is unimportant): 
, where 
is the number of times j occurs in f. We call this the partition invariant of the harmonic morphism. 
, 
, with associated
whose corresponding partitions agree, 
then we say 
and 
are partition equivalent.
examples!
, so we start with 
. We indicate a harmonic morphism by a vertex coloring. An example of a harmonic morphism can be described in the plot below as follows: 
sends the red vertices in 
, plus that induced by 
and all of its cyclic permutations (4+6=10). This set of 6 permutations is closed under the automorphism of 
and all of its cyclic permutations (4+7=11). This set of 7 permutations is not closed under the automorphism of 
and all 7 of its cyclic permutations (total = 7+11 = 18).
and all of its cyclic permutations (4+8=12). This set of 8 permutations is not closed under the automorphism of 
and all of its cyclic permutations (12+8=20). In addition, there is 
and all of its cyclic permutations (20+8 = 28). The latter set of 8 cyclic permutations of 
is closed under the transposition (0,3)(1,2) (total = 28).
and all of its cyclic permutations (4+9=13). This set of 9 permutations is not closed under the automorphism of 
and all 9 of its cyclic permutations (9+13 = 22). This set of 9 permutations is not closed under the automorphism of 
and all 9 of its cyclic permutations (9+22 = 31). This set of 9 permutations is not closed under the automorphism of 
and all 9 of its cyclic permutations (total = 9+31 = 40). 
is the graph whose SageMath command is 
then, instead of showing a graph, I’ll list the edges (of course, the vertices are 0,1,…,11) and the SageMath command for it.
, where 
.
.
.
.
.
.
.
and 
then this is a list of length 
consisting of elements taken from the 
vertices in 
.
and let 
.
by
of a graph 
, we define the star 
to be a subgraph of 
is called harmonic if for all vertices 
, the quantity
in 
.
, we may identify a Boolean function
, let 
denote the set of complements 
, for 
, and let 
denote the complementary Boolean function. Note that
denotes the complement of 
in 
. Let
is even (resp., odd). We may identify a vector in 
Let
).
denote the $2^n\times 2^n$ Hadamard matrix defined by 
, for each 
such that 
. Inductively, these can be defined by
whose 
th component is
as the column vector where the 
th component is
.
. It is even because
be the Cayley graph of 
so 
has no loops. In this case, 
-regular graph having 
connected components, where
, the set of neighbors 
of 
be the 
adjacency matrix of 
of the adjacency matrix 
) to the Walsh-Hadamard transform 
. Note that 
where 
. She discovered the relationship
be the binary Hamming [7,4,3] code defined by the generator matrix 
and check matrix 
. In other words, this code is the row space of G and the kernel of H. We can enter these into Sage as follows:
defined by 
. Using this map, the codewords are easy to describe and enumerate:
.
. This must be a codeword (no lies) or differ from a codeword by exactly one bit (1 lie). In either case, you can find n by decoding this vector.
.
in region i of the Venn diagram.
, for some unknown 
. We solve for this unknown using the check vertex equation 
. The decoded codeword is 
. In this case, we know the vertices 9 and 10 fail, so 
. We solve using 
. By majority vote, we get 
. 
, 
.
is the matrix whose entries are 
, 
is a regular graph of degree wt(f), where wt denotes the Hamming weight of f when regarded as a vector of values (of length 
).
(this only makes sense if n is even). The Hadamard transform of a integer-valued function f is an integer-valued function over 
given by 
.
given by 
.
be a weighted digraph having 
denote its
adjacency matrix. We identify the vertices with the set 
.
n-1 in row i and column j equals the length of a shortest path from vertex i to vertex j in G. (Here A
is equal to A
This verifies an example given in chapter 1 of the book by Maclagan and Sturmfels, 
be a weighted digraph having 
denote its 
adjacency matrix. We identify the vertices with the set 
, is defined with the operations as follows: 
, 
. The ordinary product of two 
operations (roughly the same number of additions and multiplications). The tropical product of two 
, where M is the complexity of computing the (tropical) product of two 
time. However, the implied “big-O” constant is so large that the algorithm is not practical. Strassen’s algorithm can multiply two 
time. 
, using Strassen’s algorithm. This is better than the 
Yet Another Mathblog 
You must be logged in to post a comment.