GLOSSARY

GRAPH: In this census, the word graph means a simple graph, a colection V of things called "vertices" and a set E of unordered pairs from V, the edges of the graph.

SYMMETRY: A symmetry, also called an automorphism, of a graph is a permutation of its vertices which preserves edges. If G is a graph, the symmetries of G form a group under composition, called Aut(G).

Graphs in this Census: This Census concerns graphs of degree 4 (tetravalent graphs) which are edge-transitive, i.e., those for which, given edges e and e', there is s in Aut(G) which sends e to e'. A dart (or arc or directed edge) is one of the two ordered pairs of vertices corresponding to an edge. If AG = Aut(G) is transitive on darts, we naturally call it dart-transitive (abbreviated DT); the word "symmetric" is often used with this meaning. If AG is transitive on edges and vertices, but not on darts, we say that G is ½-arc-transitive or HT. If AG is transitive on edges but not on vertices, we say thatG is semi-symmetric, or SS for short.

The headings in the Table and the spreadsheet version of the Census:

 Tag: The tag "C4[20,5]" means this graph is number 5 in the list of graphs having 20 vertices.

 V: This is the number of vertices

 E: The number of edges

 Transitivity or Tr.: This tells which of three kinds of symmetry the graph has. We abbreviate the types DT (dart-transitive), HT for ½-arc-transitive, SS for semisymmetric.

 Worthy? or W?: W or U as the graph is worthy or not. (A graph is unworthy if some two of its vertices have exactly the same neighbors; it is worthy otherwise.)

 Bipartite? or B?: B or NotB as the graph is bipartite or not.

 AG: The order of the symmetry group.

 vs: The order of a vertex stabilizer.

 ds: The order of a dart stabilizer.

 gi: The girth of the graph.

 dm: The diameter of the graph

 Name: The canonical (i.e., first-chosen) name for the graph. This shows the parameters of one construction for it. Others are listed on the graph's Constructions page.

CIRCULANT GRAPHS: The circulant graph C_N(S) is defined for any integer N at least 3, and every subset S of Z_N which is closed under negation. The vertices are the elements of Z_N, and i, j are joined by an edge exactly when j-i is in S. We usually abbreviate by listing only those s in S which are less than or equal to N/2. Thus K₅ is C₅(1,2). The degree-4 edge transitive circulants are all C_2M(1,M-1) and all C_N(1,a), where a² is 1 or -1 mod N.

WREATH GRAPHS: The vertices of the wreath graph W(N, k) come in N bunches of k each, the bunches arranged in a circle. Each vertex in bunch i is joined by an edge to each vertex in bunch i-1 and bunch i+1. The depleted wreath graph, DW(N, k) is formed from W(N, k) by removing the edges of k disjoint N-cycles. Of these, only W(N, 2) and DW(N, 3) are tetravalent.

TOROIDAL MAPS: There are three families of maps of type {4, 4} on the torus in which the symmetry group of the map acts transitively on the edges. One is the well-known family of regular maps {4, 4}_b,c. These are formed from {4, 4}, the grid of squares, by identifying to vertices whose coordinates differ by an element of the group generated by vectors (b, c) and (-c, b). This map has D = b² + c² vertices, D faces and 2D edges. The second is {4, 4}_<b,c> formed in a similar way; the group in this case is generated by (b, c) and (c, b). This map has D₂ = |b² - c²| vertices, D₂ faces and 2D₂ edges. The third is {4, 4}_[b,c] formed similarly; the group in this last case is generated by (b, b) and (c, -c). This map has D₃ = 2bc vertices, D₃ faces and 2D₃ edges. These maps and graphs were classified by Siran, Tucker and Watkins.

SPIDERGRAPHS: The Power Spidergraphs were named by Leah Berman. PS(k, n; r) is defined for k, n, r satisfying r^k = 1 or -1 (mod n). Vertices are in Z_kxZ_n. Edges join each (i,j) to (i+1, j±rⁱ). MPS(k, n; r) is similar, but n is even and (k-1, j) is joined to (0, j±r^k-1 + n/2).

GPS2 This construction is a special case of one due to Casey Attebery. It is a 2-dimensional Generalized Power Spidergraph. GPS2(k, n, M) has vertices in Z_kxZ_nxZ_n, and M is a 2x2 matrix over Z_n. For i in Z_k and x in Z_nxZ_n, (i, x) is joined to (i+1, x+a_i) and (i+1, x+b_i), where a_i = (1, 0)Mⁱ and b_i = (-1, 0)Mⁱ.

BICIRCULANT GRAPHS: A bicirculant graph is one on 2n vertices which allows a symmetry moving them in 2 cycles of length n. There are two kinds of tetravalent edge-transitive bicirculants. One is the Rose Window graphs (see below). The other bi-circulant graph is BC_n(S) is defined for any integer n at least 3, and every subset S of Z_n. The vertices are all A_i, B_j for i, j in Z_n. A_i, B_j are joined by an edge exactly when j-i is in S. The logo for this Census is BC₇(0, 1, 2, 4). Each BC_n(S) is a Cayley graph of a dihedral group.

Rose Window Graphs: The graph R_n(a, r) = R_n(a,r) has 2n vertices: A_i and B_i for i = 1, 2, . . . , n. There are 4 kinds of edges:
(1) Rim: {A_i,A_i+1}
(2) Spoke in:{A_i,B_i}
(3) Spoke out:{B_i,A_i+a}
(4) Hub:{B_i,B_i+r}

These are known to be edge-transitive in 4 cases:
(1) R_n(2,1) This is the same as W(n, 2)
(2) R_2m(m+2,m+1)
(3) R_2m(2b,r), where b² = + or -1 (mod m) and r = 1 or m is even and r = m+1. Exclude graphs in families (1) and (2) from family 3. We separate family 3 into family 3a (where b² = 1 (mod m)) and family 3b (where b² = -1 mod m).
(4) R_12M(3M+2,9M+1), R_12M(9M+2,3M+1). Again we separate into two families: 4a is the case where M is odd, 4b where n is even.

Every R_N(a, r) for n up to 100 which is edge-transitive belongs to one of these families. Recently Istvan Kovacs has announced a proof that this holds for all n.

BICYCLE WHEELS: The graph BW_n(a, r, s) = BW_n(a,r,s) has 3n vertices. They are A_i, B_i and C_i for i = 1, 2, . . . , n. There are 4 kinds of edges:
(1) Rim: {A_i,B_i},{B_i,A_i+1},
(2) Inner Spokes: {B_i,C_i},{C_i,B_i+a},
(3) Outer Spokes: {A_i,A_i+r}
(4) Hub: {C_i,C_i+s}.

Not many of these are edge-transitive (those which are must, as a result, be dart-transitive). Investigation is in motion to determine/predict which n, a, r, s give edge-transitive graphs.

Marušič and Šparl: The paper "On Quartic Half-arc-transitive Metacirculants" contains two new families of interest to this Census. They are called Y and Z in that paper, and we will cal them MSY and MSZ here.

MSY(m,n;r,t) has vertices Z_mxZ_n; its edges are all pairs {(i,j), (i, j+rⁱ)} and all pairs {(i,j), (i+1, j)} except when i is m-1, and then the edge is {(m-1,j), (0, j+t)}. The paper discusses which values of the parameters make the graph HT. It can also be DT, and it can be an LR structure. If m = 2, then MSY[2, n; r, t] is isomorphic to the Rose Window graph R_n(t, r); if r = 1, the graph is toroidal. There are some 10 other dart-transitive MSY graphs in this census. At the moment it is an open question (we have no idea, really) which parameters cause the graph to be dart-transitive.

When the graph is not dart-transitive, it might still be an LR structure. One possibility is that r = 1 or (r = t-1 and n = 2t), in which case the LR structure is toroidal and so its Partial Line graph is then a dart-transitive toroidal graph. MSY graphs in which m is even and r² is 1 or -1 are Barrel LR structures, but there are many MSY LR graphs for which this does not hold. Again, work is in progress to find out which parameters work in this way.

MSZ(m,n;k,r) has vertices Z_mxZ_n; its edges are all pairs {(i,j), (i+1, j)} and all edges {(i,j), (i+k, j+rⁱ)}. The paper discusses which values of the parameters make the graph HT. It can also be DT, and it can be an LR structure. Much less is known or even conjectured about this family.

FOSTER CENSUS: The graphs referred to as, for example, L(F20A) are line graphs of graphs from the Foster Census, as presented by Conder, et al. There are three constructions which use the Foster Census:

Line Graph: If X is a cubic graph, L(X) has one vertex for each edge of X, and two of these vertices are joined if the corresponding edges are adjacent; i.e., have a point in common.

Dart Graph: If X is a cubic graph, DG(X) has one vertex for each directed edge (u,v) of X, and each (u, v) is joined to each (v, w), where u, w are distinct neighbors of v.

Hill Capping: If X is a cubic graph, DG(X) has four vertices {u₀, v₀},{u₀, v₁},{u₁, v₀},{u₁, v₁}, for each edge {u,v} of X, and each {u_i, v_j} is joined to each {v_j, w_1-i}, where u, w are distinct neighbors of v.

CYCLE DECOMPOSITIONS: A Cycle Decomposition D of a tetravalent graph is a partition of its edges into cycles. The Partial Line Graph PL(D) of a cycle decompostion D is a graph whose vertices are the edges of D. Two are joined by an edge if they meet at a vertex but belong to different cycles in D.

A Cycle Decomposition D is Cycle Structure provided that the subgroup of symmetries which preserve D act transitively on the darts of the graph. PL of a Cycle Structure is vertex- and edge-transitive. In the Table, we denote a cycle structure having k cycles of length n on the graph G by G[n^k].

A decomposition is Bipartite provided that the cycles can be partitioned into two classes ("red" and "green") so that each vertex belongs to one cycle from each class. An LR Structure is a bipartite cycle decomposition with some non-triviality conditions in which the stabilizer of an edge and a vertex has a symmetry which interchanges edges of the other cycle at that vertex. PL of an LR structure is always semisymmetric.

One family of LR structures are the Barrels: Br(k, n;r) is defined for k, n, r satisfying: k is even, r² = 1 or -1 (mod n) but not r = 1 or -1 (mod n). Vertices are in Z_kxZ_n. Edges in one class are of the form {(i,j), (i+1, j)}; in the other are {(i, j), (i, j+rⁱ)}.

A related graph is the Mutant Barrel, MBr(k, n;r). Here, n must be even and the edges {(k-1,j), (0, j)} are replaced by {(k-1,j), (0, j+n/2)}.

If D is a cycle structure, CS(D,k), CSI(D,k), CSII(D,k) are LR structures which are covers of the multigraph formed from D by replacing each vertex with two vertices, one in each cycle of D, the two copies of v being joined by two parallel edges.

RC: RC(k,n) is an LR structure whose vertex set is the union of (Z_nxZ_k)xZ_n and Z_nx(Z_kxZ_n). Green edges join (i, (r, j)) to (i + 1, (r, j)) and ((i, r), j) to ((i, r), j + 1), while red edges join (i, (r, j)) to ((i, r + 1), j) and so ((i, r), j) to (i, (r + 1, j)).

SoP: SoP(k, n) is an LR structure whose vertex set is Z_kxZ_nxZ₂, where k and n are divisible by 4. Let r = (n/2+1). Red edges are all {(i,j,L), (i, j+r^L, L)}; green edges join the two vertices (2i,j,0) and (2i,j,1) to the two vertices (2i+1,j,0) and (2i+1, j, 1) if j is even, to the two vertices (2i-1,j,0) and (2i-1, j, 1) if j is odd.

BGCG stands for the Base Graph - Connection Graph Construction, which is not yet a construction. Given a tetravalent dart-transitive "base graph" B and a k-valent dart-transitive "connection graph" C, we can often form a graph G from them by doing the following:

(1) Form B' from B by "subdividing" each edge, i.e., by replacing each edge with a path of length 2. Think of the original vertices as black, the new ones as white.

(2) For each vertex r of C, make one copy B_r of B'.

(3) For each edge {r, s} of C, identify some of the white vertices with of B_r with some of the white vertices of B_s.

If this is done in a sufficiently nice way, the resulting G will be edge-transitive. It will always be bipartite and may be semisymmetric.

There are four cases we know about so far in which the "construction" is well-defined and gives edge-transitive G. All four of them rely on the idea of dart-transitive colorings. Consider a coloring g of the edges in a graph G. Let Aut(G, g) the group of symmetries which, for each color, send all edges of that color to all edges of that or some other color. If Aut(G, g) is transitive on the darts of G, we call g a dart-transitive coloring.

[1] The Color Construction: suppose that b is a dart-transitive coloring of B and g is a dart transitive coloring of C by the same colors. Suppose further that every vertex in C meets exactly one edge of each color. If edge {u, v} of B has color c and edge {r, s} of C also has color c, identify the white vertex corresponding to {u,v} in B_r with the white vertex corresponding to {u,v} in B_s. Call the resulting graph BGCG(B, b, C, g).

[2] Chain: if b₁ is a coloring of B in 2 colors and b₂ is a coloring of B by n colors, where n is the number of vertices of B, and each of the colors in b₂ has one edge of each color in b₁, we can let C be a k-cycle and identify each edge of b₁-color c in B_r with the other edge of color c in B_r+1. Call the resulting graph BGCG(B, b, C_k).

[3] Loop: if b is a coloring of B by n colors, we can let C be a loop, a graph with one vertex v and one edge joining v to itself. Then G is the result of identifying each white vertex in B_v with the other white vertex of that color. Call the resulting graph BGCG(B, b, C₁).

[4] Edge: if b is a coloring of B by n colors, we can let C be a 1-path, a graph with two vertices u and v, and one edge joining them. Then G is the result of identifying each white vertex in B_u with the other white vertex of that color in B_v. Call the resulting graph BGCG(B, b, K₂).

A graph B may have several non-isomorphic edge-colorings. Until we can devise a way to give these expressly, we will call the colorings 1, 2, etc, and denote the graphs in [3] and [4] by BGCG(B, i, C₁) and BGCG(B, i, K₂).

OTHERS Other cryptic notations: 2AT, PPDT, PPSS, A4s, A4x, S4, Z4, MCA refer to the results of computer searches to find graphs with edge-transitive subgroups having certain relatively small vertex-stabilizers. Each graph with a name from this list is a mystery. The challenge is to understand the graph sufficiently to generalize it to an infinite family.

CONSISTENT CYCLES One of the best-kept secrets in graph symmetry is the Biggs-Conway result about consistent cycles. A cycle C is consistent provided that there is a shunt for it, a symmetry of the graph which moves each vertex of C to the next vertex in order along C. Biggs and Conway proved that in a dart-transitive graph of degree d, there are exactly d-1 orbits of consistent cycles. Potočnik and Miklavič have generalized this result in several ways. In a half-transitive graph of degree 2d, there are exactly d orbits of consistent cycles.

DISTANCE-ORBIT CHART If u is a vertex, the stabilizer of u has orbits of various sizes on the vertices at distance 0, 1, 2, . . . from u. The chart for each graph shows the number of orbits of each size at each distance. If the graph is semisymmetric, adjacent vertices may have different actions, and both are given.

GENERALIZED IVANOV VECTORS In a semisymmetric graph of degree d and girth 2r, fix a vertex u. The vector for u is a, where a_i is the number of vertices connected to u by exactly i paths of length r. All vertices u in one Bipartition class will have the same vector, as will all v in the other class. If r is odd, these two vectors will be equal, while if r is even, they may not be.

SEMIREGULAR SYMMETRIES A symmetry of a graph is semi-regular provided that it permutes the vertices in orbits of a single size. If a graph admits such a symmetry of k-cycles, it clearly also admits such symmetries in d-cycles for all divisors d of k. On the page for each graph, we list only the maximal cycle lengths. For instance, the entry for a graph might say "6¹⁰, 15⁴, 20³", meaning that it has a symmetry consisting of ten 6-cycles, one of four 15-cycles and one of three 20-cycles. Of course, these imply the existence of semiregular symmetries of orders 1, 2, 3, 4, 5, 10 as well.

CYCLIC COVERINGS Each semiregular symmetry allows us to regard the graph as a cyclic covering of some smaller graph. If the symmetry includes the cycles (u₀, u₁, u₂, . . . u_n-1)(v₀, v₁, v₂, . . . v_n-1) and {u₀, v_a} is an edge, then every {u_i, v_a+i} is an edge, and we can make a graph including the vertices u and v and the label a on the edge {u, v}. On the Constructions page for each graph, we provide such a diagram in the form of a skew symmetric matrix of sets of numbers mod n. The numbers in row u, column v are all the weights of edges from u to v.

For example, the matrix:

Stands for the diagram: