Technical Terms:
abelian, Aut G, automorphism, Cayley color graph, complement, composition, congruent, contrapositive, cyclic group, degree sequence, direct product, F-diagram, group, identity, invariant, inverse, isomorphism, Klein four-group, modulo, octahedron, one-to-one, permutation, rotation, reflection, self-complementary, subgroup, transformation, transposition, wreath product
Link to Chapter 8.
Whether in nature or in mathematics, the search for symmetry is universal. If asked to draw a polygon, it is natural, for many, to try to draw a regular polygon. Symmetry is often reassuring, in some way. Graph theorists tend to draw triangles as equilateral since only connection pattern is important. Since symmetry is important, a wealth of mathematical machinery exists to measure it. In calculus, one studies derivatives of functions f(x) with the name of the function f written to the left of the element x that it transforms. Much as postscript (or reverse Polish) notation simplifies mathematical expressions and eliminates the need for parentheses, so writing functions on the right will simplify notation. Therefore so-called right-hand notation will be employed in this chapter.
If A and B are two sets, a function (or transformation) f: A → B assigns to each element of A an element af in B. The function f is called one-to-one if a ≠ b implies af ≠ bf. The function f is called onto if every b in B is af for some a in A.
Usually one shows a function is one-to-one using the contrapositive of the definition. That is, one shows that af = bf implies a = b.
For example, suppose Z is the set of integers. Define f: Z → Z by letting nf = n + 3 for any integer n.
Suppose f: A → B and g: B → C are functions. Then the composition fg: A → C is defined by the rule a(fg) = (af)g. Diagrammatically, composition is illustrated as in Figure 8c.1.
Figure 8c.1. This figure presents a diagram showing composition of functions.
Theorem 8c.1. If f: A → B and g: B → C are one-to-one, then fg is one-to-one.
Proof: Suppose x(fg) = y(fg). Then (xf)g = (yf)g. Therefore, xf = yf since g is one-to-one. Thus x = y since f is one-to-one.
Theorem 8c.2. If f: A → B and g: B → C are onto, then fg is onto.
Proof: Since g is onto, given c ∈ C, there is an element b ∈ B with bg = c. But since f is onto, there exists a ∈ A with af = b. But then a(fg) = (af)g = bg = c, so fg is onto.
A function that is both one-to-one and onto is called a one-to-one correspondence; the above theorems, 8c.1 and 8c.2, show that the composition of two one-to-one correspondences is a one-to-one correspondence. If f is a one-to-one correspondence from A to B one can define an inverse one-to-one correspondence g: B → A by bg = a if and only if af = b.
Let G = (V1, E1) and H = (V2, E2) be two graphs. The graphs G and H are said to be isomorphic if there is a one-to-one correspondence f between V1 and V2 that induces a natural one-to-one correspondence between E1 and E2. An invariant of a graph G is a number associated with G that has the same value for any graph isomorphic to G. A complete set of invariants determines a graph up to isomorphism.
To see, by inspection, whether or not two graphs are isomorphic can be quite difficult. The octahedron is a simple geometric solid, formed by gluing two pyramids (with square base) together across their bases. The graph of the solid octahedron is often viewed as a side view of the solid or as a polar view of the solid (Figure 8c.2a shows a side or orthographic view). It is also represented as a graph in Figure 8c.2b. It is not difficult to see that these two views of the octahedron are isomorphic, even though the first one has edges that cross in the plane and the second one does not. When IBM (International Business Machines) was configuring three-bus patterns, so the story goes, it was, however, quite a discovery process for them to see that two three-buses, together with needed interconnections between the buses, was in fact isomorphic to an octahedron (Figure 8c.2c). The Grapphlet in Figure 8c.3 will settle to any of Figures 8c.2a, 8c.2b, or 8c.2c, depending on how it is scrambled. The graph within a Grapphlet at any instant is isomorphic to all other graphs within that Grapphlet.
a. |
b. |
c. |
Figure 8c.2. a. Octahedron, side view. b. Graph of octahedron. c. Two three-buses, in blue, with suitable interconnection (hexagon) in yellow.
Figure 8c.3. This Grapphlet shows a range of graphs isomorphic to the octahedron. The sides are drawn in varying lengths to illustrate variety in pattern: geometric symmetry is deliberately destroyed to enable the Grapphlet to settle in a variety of positions. Sun Microsystems, Java™. Source: Graph.java.
Used with permission from Sun Microsystems, Inc. Copyright 1998-2001 Sun Microsystems, Inc. All rights reserved.
Ulam's Conjecture. Let G have n nodes vi and H have n nodes ui, with n ≥ 3. If for each i, the subgraphs Gi = G - vi and Hi = H - ui are isomorphic, then the graphs G and H are isomorphic.
The conjecture suggests that the set of subgraphs of a graph offer quite a bit of information about the graph itself (as with the real-world analogy that the trees in the forest offer information about the forest itself).
Example. It is easy to show that the two graphs of Figure 8c.4 are isomorphic, for the function xf = x + 4 is an isomorphism.
Figure 8c.4. This figure shows two isomorphic graphs.
One often wants to study those ways in which a given graph is isomorphic to itself. Isomorphisms of a graph with itself are called an automorphisms. The mathematical structure most appropriate for studying automorphisms is the group.
A group G is a set of objects together with a binary operation * on G such that
For example, if G is the set of integers, and * is addition, G together with * form a group. In fact, since a + b = b + a for every two integers, this group has the additional property of being abelian.
A group G is called abelian if for every a, b ∈ G, a * b = b * a.
Any subset H of G that is itself a group under the same operation as G is called a subgroup of G.
The most familiar groups one first encounters involve familiar operations like addition and multiplication. The integers, rational numbers, and real numbers are all groups under addition. The non-zero rational numbers and non-zero real numbers form groups under multiplication (where the inverse of x is 1/x).
However, in studying symmetry of structures, the relevant operation is composition of functions, and the group elements are themselves functions. Indeed, we have already shown the following theorem.
Theorem 8c.3. Let G be a graph. Let Aut G be the set of all automorphisms of G. Then Aut G is a group under the operation composition of functions.
A group is infinite if it has an infinite number of elements. If G has a finite number of elements, we say G has order n, written |G| = n.
If a ∈ G, a * a is denoted a2; in general ak = a * ak-1 if k is a positive integer greater than one; a-k = (a-1)k = (ak)-1. The usual rules of exponents hold.
The cyclic group generated by a, denoted <a>, is the set of all powers of a. If G is finite of order n, and a ∈ G, |<a>| is a divisor of n. If for some a ∈ G, G = <a>, G is itself called cyclic. In general, the order of a, denoted o(a), is |<a>|. Clearly any cyclic group is abelian.
The set of integers Z under addition is a cyclic group; Z = <1>.
If n is a positive integer, a is said to be congruent to b modulo n, written a ≡ b mod n, if n is a divisor of a - b. Congruence is an equivalence relation that partitions the integers into n different classes:
[0] = {k | k ≡ 0 mod n} = [n] = [2n] = ...
...
[n - 1] = {k | k ≡ n-1 mod n}
If a ≡ b mod n, [a] = [b].
If addition on classes is defined by [a] + [b] = [a+b], the set of equivalence classes forms a cyclic group called the integers mod n, denoted Zn = <[a]>.
Two groups, G, H are called isomorphic if there is a one-to-one correspondence f: G → H such that g1, g2 ∈ H implies (g1 * g2)f = g1f * g2f. Thus, all cyclic groups of order n are isomorphic, since if <a> = <b> are two cyclic groups of order n, the mapping af = b is an isomorphism. If G is isomorphic to H, we write G ≅ H.
In general, we will write Zn for any cyclic group of order n, and usually we will use multiplication as the (implied) operation, so that Zn = {a, a2, ... , an-1, e} where e = a0 = an and the usual rules of exponents hold. We shall hold to this convention even when the operation is in fact composition of functions, as it will be in the material on automorphisms of graphs.
Let G, H be two groups with operations *g and *h. Then a new group G x H, the direct product of G and H, is defined on the set of ordered pairs (g,h), g ∈ G, h ∈ H by
Note that (eg, eh) = e, the identity in G x H.
If |G| = m, |H| = n, then |G x H| = mn. In fact, if g ∈ G with o(g) = s and h ∈ H with o(h) = t, then o(g, h) is the least common multiple of s and t.
More extensive discussion of the fundamentals of group theory can be found in any text on modern algebra (e.g. Herstein 1964 or Fraleigh, 1994) or group theory (Gorenstein 1968). Either text would discuss and prove the following important theorem.
Theorem 8c.4 (Fundamental Theorem of Finite Abelian Groups). Let G be a finite abelian group of order n = p1a1p2a2 ... pkak, where p1, ..., pk are the prime divisors of n. Then G is isomorphic to a direct product of cyclic groups of prime power order. Further, the sum of the exponents of the powers of all the groups of order a power of pi is in fact ai.
For example, if |G| = 15 and G is abelian, then G ≅ Z3 x Z5 ≅ Z15. On the other hand, there are three possibilities for an abelian group of order 8: Z8, Z4 xZ2, and Z2 x Z2x Z2.
Since every automorphism of a graph is a function that is a re-naming of the nodes of that graph, it is natural to study such one-to-one correspondences. Let S = {1, ..., n}. A permutation of the elements of S is an ordering of the n elements in S. Since this ordering gives a sequence of elements in S, it can be represented by a one-to-one correspondence from S to itself. For example, if S = {1,2,3,4}, the permutation 2,1,4,3 is represented by the function f with 1f = 2, 2f = 1, 3f = 4, 4f = 3. There are clearly n! permutations of S, and the composition of any two permutations. The permutation that lists the elements of S in natural order serves as an identity i for the set S under the operation composition, and being a one-to-one correspondence, each permutation f has an inverse f-1 with ff-1 = f-1f = i. Therefore, we have shown the following theorem:
Theorem 8c.5. Let Sn be the set of permutations of {1,...,n}. Then Sn is a group of order n! with the operation composition.
There are many notations for permutations. Perhaps the most useful is called cycle notation. We illustrate this with an example. Suppose f is the permutation in S5 with 1f = 2, 2f = 4, 4f = 1, 3f = 4, and 5f = 3. Notice that rather than listing f(1), f(2), ..., f(5) in sequential order, we listed 1f, 1ff, 1fff,... until one of these values returned to 1. Then we selected another element 3 and listed 3f and 3ff.
We can execute this procedure without writing f at all by just writing the corresponding numbers in parentheses, as f = (124)(35). Within a parenthesis, f transforms the first element to the second, the second to the third, ..., and the last to the first. Thus as before 1f = 2, 2f = 4, and 4f = 1; 3f = 5 and 5f = 3.
This notation is not unique. Consider the permutation (124); since the elements within parentheses are transformed in cyclic fashion, it follows that (124) = (241) = (412). In fact, a cyclic set within parentheses (a1 a2 ... ak) is called a k-cycle.
Any permutation can be written as a product of disjoint cycles by the process described in the example. The identity is e = (1)(2)...(n). In writing a permutation, 1-cycles are often omitted, and any elements not listed in a cycle are presumed fixed by the permutation.
Thus, in S5, the permutation (1 5)(2 3) fixes 4. For simplicity, then, we write e = (1).
This cycle notation is useful in computing the composition of permutations.
Example.
Suppose f = (123)(45) and g = (134)(25). Then fg = (123)(45)(134)(25), and it is easy to write fg as a product of disjoint cycles by following this cycle product:
1 is sent by (123) to 2
2 is unchanged by (45)
2 is unchanged by (134)
2 is sent by (25) to 5.
Thus 1fg = 5.
Continuing in this fashion, we compute 5fg = 1, since
(45) sends 5 to 4
(134) sends 4 to 1
Thus, we can compute fg = (15)(24). Note that 3 is fixed by fg.
Theorem 8c.6. Any permutation in Sn can be written as a product of transpositions.
Proof: It is necessary to show only that any cycle is a product of transpositions. We have that
(a1 a2 ... ak) = (a1 a2)(a1 a3)(a1 a4) ... (a1 ak).
Thus, any k-cycle is a product of k-1 transpositions. In fact, if a permutation can be written as a product of transpositions in two different ways, such as (1 2 3) = (1 2)(1 3) = (2 3)(2 1), then the number of transpositions is either odd or even in each case.
In fact, exactly half of the permutations in Sn are even and half are odd. The set of even permutations forms a group An, a subgroup of Sn. Since e = (1 2)(2 1) is even, the set of odd permutations cannot form a group. The group An is of considerable importance in group theory. Texts on modern algebra or group theory will contain substantial amounts of information on it (e.g. Herstein, 1964; or, Fraleigh, 1994). For our part, since every automorphism of a graph is a permutation of its set of nodes that preserve adjacency, the set of automorphisms of a graph with n nodes is a subgroup of Sn.
Suppose G is a graph with n nodes. Choose a labeling 1, ..., n of the nodes. Then any automorphism of G is a subset of Sn such that if f is such an automorphism uv is an edge in G if and only if uf,vf is an edge in G. That is, f preserves edges.
The set of all automorphisms of G will be denoted Aut G. Aut G will be computed for several graphs.
Figure 8c.5.
The above case illustrates an obvious idea: if v is a node in G, and f ∈ Aut G, then deg (v) = deg(vf). Otherwise it would be impossible to preserve all edges (assumes G is finite).
Figure 8c.6.
In G1 the two nodes of degree one may be interchanged, as may the nodes of degree zero. Thus Aut G1 = {(1), (1 4), (2 3), (1 4)(2 3)} ≅ Z2 x Z2. This group is sometimes know as the Klein four-group and is the only non-cyclic group of order 4.
Figure 8c.7.
Since the node 4 must remain fixed, and the path is either fixed or inverted, Aut G2 ≅ Z2. Note Aut G2 = {(1), (1 3)}, a subgroup of S4.
Figure 8c.8.
Either path of G3 may be reversed, independent of each other, and either path may be mapped to the other. Alternatively, in G3c, the square may be rotated through 90 degrees, 180 degrees, or 270 degrees, and there are four reflections (1 2)(3 4), (1 4)(2 3), (1 3), and (2 4) about lines between midpoints of opposite sides or about diagonals of the square. Thus Aut G3 = {(1), (1 2 3 4), (1 3)(2 4), (1 4 3 2), (1 2)(3 4), (1 4)(2 3), (1 3), (2 4)}. Note that Aut G3 contains a subgroup {(1), (1 2 3 4), (1 3)(2 4), (1 4 3 2)} ≅ Z4. The group Aut G3 is called the dihedral group D4 of order 8. More will be said later about this group.
Figure 8c.9.
From 1), it follows that Aut G4 ≅ S3. In fact, Aut G4 = {(a), (1 2 3)(4), (1 3 2)(4)}, a subgroup of S4 isomorphic to S3. It is easy to see that Sn contains a subgroup isomorphic to Sk for any k < n. One such subgroup consists of all permutations of the first k integers, with the remaining n-k fixed. Of course any set of n-k integers could be fixed, instead of the last ones. Notice that in this case G3 and Gc had the same number of edges as each other. When this happens, on occasion a graph and its complement are isomorphic. A graph whose complement is isomorphic to it is called self-complementary.
Figure 8c.10.
Several ideas have been introduced through these examples, and some of them will be used later in this chapter.
Earlier, in Figure 8c.2, it was seen how difficult it is to recognize when two graphs are isomorphic. However, the language of groups has at least made the problem accessible. If G1 = (V1,E1) and G2 = (V2,E2) are isomorphic graphs, there must be a one-to-one correspondence f:V1 → V2 such that vw ∈ E1 if and only if vf, wf ∈ E2. This if and only if provision was not evident when we considered automorphisms, since the edge sets were automatically the same size, and it was sufficient for vw ∈ E to imply vf,wf ∈ E. However, for isomorphisms, this is not the case. Consider the case of G1 and G2 as in Figure 8c.11.
Figure 8c.11.
Here the identity mapping is a one-to-one correspondence that preserves every edge of G1. However, the edge 1,4 is in G2, and its inverse image 1,4 is not an edge in G1. Therefore, properly, this mapping is not an isomorphism of the two graphs.
It was shown in the previous section that if f is an isomorphism between G1 and G2, and v ∈ V1, then deg (v) = deg (vf). The degree sequence of a graph is a list of the degrees of the nodes of that graph, in descending order. Referring back to Figure 8c.11, G1 has degree sequence 2,2,2,2 and G2 has degree sequence 3,3,2,2. Since deg (v) = deg (vf) for any node, when f is an isomorphism, we have the following theorem.
Theorem 8c.7. If G and H are isomorphic graphs, they have the same degree sequence or, equivalently, degree sequence is an invariant of a graph G.
Degree sequence can be used to distinguish graphs that are non-isomorphic. For instance, the eleven graphs with four nodes all had different degree sequences. Unfortunately, however, there are non-isomorphic graphs that have the same degree sequence. For example, each of the two graphs of Figure 8c.12 has degree sequence 2,2,2,2,2,2 but they are not isomorphic to each other.
Figure 8c.12.
Trees provide a rich source of graphs with identical degree sequences that are non-isomorphic (Harary and Prins, 1959). Consider the two trees of Figure 8c.13.
Figure 8c.13.
Each has degree sequence 3,3,2,1,1,1,1. However, in the first graph the nodes a and b of degree 3 are adjacent. Since the nodes of degree 3 in the second graph are not adjacent, no one-to-one correspondence f from the first node set to the second node set can leave af, bf an edge.
Judicious use of degree sequence can help to find candidates for isomorphic graphs. Nevertheless, as the above examples illustrate, the matter remains complex.
Geometrically, one figure that has been of interest since antiquity is the regular n-gon, a figure with n sides of equal length with the angles at each vertex of identical size. Of course, the simplest examples are the equilateral triangle and the square. Since graphs deal with adjacencies rather than with lengths of edges or angles, they are ideal for studying automorphisms of these geometric figures. Any triangle is the same; automorphisms are unaffected by geometric shape.
Figure 8c.14.
We know its automorphism group is S3. But it consists of three rotations (1), (1 2 3) (120 degrees counterclockwise) and (1 3 2) (240 degrees counterclockwise) along with reflections through the three dashed lines (1 2), (1 3), and (2 3). Indeed, the composition of two reflections is a rotation (Figure 8c.15).
Figure 8c.15.
If f is the rotation (1 2 3) and g is the reflection (1 2), then gf = (1 3) = f -1g = f 2g. Using the formula, every element of the automorphism group of the triangle can be written in the form f agb, 0 ≤ a ≤ 2, 0 ≤ b ≤ 1. (The identity is f 0g0.) Thus we can say that this group is generated by two elements f and g which satisfy the relation f3 = e, g2 = e, and gf = f2g. For more on groups defined by generators and relations, see Coxeter and Moser (1965).
Figure 8c.16.
This square is known from our study of four-node graphs to be the group D4, called a dihedral group of order 8. It consists of a subgroup isomorphic to Z4 consisting of the four rotations (1), (1 2 3 4), (1 3)(2 4), and (1 4 3 2) along with the reflections through the four dashed lines of Figure 8c.16 (1 2)(3 4), (1 4)(2 3), (1 3), and (2 4). Again, if f = (1 2 3 4) and g = (1 2)(3 4), gf = (1 3) = f -1g =f 3g. So every automorphism is of the form f agb, 0 ≤ a ≤ 3, 0 ≤ b ≤ 1.
Thus, like the cyclic group Zn, the dihedral group Dn arises naturally. Indeed, geometrically it is more natural than Zn. Note that D3 = S3 but that Dn is much smaller than Sn for n>3.
Another question that arises is: given an abstract group, does some graph exist with automorphism group isomorphic to it? Surprisingly, the answer is always yes (Frucht, 1938). The method Frucht used begins by assigning a color to each element, then producing a directed graph called the Cayley color-graph, and then replacing each colored arc by a tree (the trees have increasing numbers of nodes as the number of colors increases). The graphs thus become large very quickly. Frucht's graph with automorphism group Z3 already has 45 nodes.
Thus, the next natural question became: how small can the graph be made with given group. Attention has focused mainly on finding a graph with as few nodes as possible. The easiest groups to consider are the cyclic groups. Either graph with two nodes has automorphism group Z2. When possible, a connected graph is probably preferable, so the one-edge graph with two nodes is the preferred choice.
Let α(G) be the smallest number of nodes possible in a graph whose automorphism group is Z2. So α(Z2) = 2.
Already with Z3, problems occur. The natural choice, the equilateral triangle, has automorphism group S3. The problem is to add enough graphical structure to eliminate reflections. It turns out that if G has six nodes labelled 1, ..., 6 and an automorphism (123)(456), then the reflection (13)(46) remains an automorphism (Arlinghaus W. 1985, Lemma 3.2). No cycles of length other than one or three can occur in an automorphism if the group is to be Z3, and nodes left fixed do not impede the opportunity. Thus the smallest possible graph must have at least nine nodes. Figure 8c.17 gives an example illustrating that α(3) = 9. The graph there has automorphism group <(123)(1'2'3')(1''2''3'')>. The diagonals prevent reflections.
Figure 8c.17.
This graph was presented by Harary and Palmer (1966), although the fact that α(Z3) = 9 was known to Sabidussi (1959) and Meriwether (1963). Sabidussi and Meriwether both attempted to solve the problem for cyclic groups and extend the results to finite abelian groups. Sabidussi succeeded only for groups of prime order, and Meriwether's results depended heavily on doubly transitive permutation groups and were not easily deciphered. The full exposition for cycles groups and its correct extension to finite abelian groups is due to Arlinghaus (1985).
Of course, a figure built on the regular n-gon, just as Figure 8c.17 is built on the triangle, would give a graph with 3n nodes and automorphism group Zn. Thus, it follows that α(Zn) ≤ 3n. In fact α(Z5) = 15, but that is the only other value of n for which 3n is the least possible number of nodes.
For numbers n that are composite, Figure 8c.18 gives an example of what might occur. The figure built on a 15-gon similar to the triangle of Figure 8c.17 would have 3(15) = 45 nodes. The two-component graph of Figure 8c.15 has only 24 nodes but still has group Z3 x Z5 ≅ Z15. Illustrating the graphs that give α(Zn) for other cyclic groups will require an aid to representing graphs first developed by Frucht (1970) and refined by Arlinghaus (1985, Chapter 2), who named them F-diagrams in honor of Frucht.
Figure 8c.18.
Drawing a triangle is easy. Drawing a 27-gon is more difficult. However, in Frucht's notation, they are equally easy.
Figure 8c.19. a) left: F-diagram of a triangle b) right: F-diagram of a 27-gon.
An encircled number n represents n labeled nodes. A number k in parentheses next to n represents edges from each of the nodes to the node labeled k above it modulo n. So in Figure 8c.19a, 1 is joined to 2, 2 to 3, and 3 to 1 (since 3+1 ≡ 1 mod 3). In Figure 8c.19b, 1 is joined to 2, ..., 26 to 27, 27 to 1. This notation is restricted to graphs so all edges are undirected.
The utility of F-diagrams comes when several sets of nodes are used. In Figure 8c.20a there are three sets of three nodes each, and each node of a set is joined to its like-labelled nodes in the other two sets. The result is the graph of Figure 8c.20b.
Figures 8c.20. a) left b) right
To achieve the graph of Figure 8c.17, further edges are needed. For instance, in Figure 8c.17, the node 1 is adjacent to 3'. So, an arrow is added along with the number 2 to indicate that each node is adjacent to a node with a number 2 larger in its corresponding set. Thus a is adjacent to a' and (a+2)' modulo 3. Then Figure 8c.21 represents the graph of Figure 8.17. (Notice that a line between circles with no number and a directed line with number 0 mean the same thing.)
Figure 8c.21.
The examples so far have used the same numbers inside the circles. If the encircled numbers are m and n, then the congruences are modulo the greatest common divisor. Thus the F-diagram of Figure 8c.22 represents the bipartite graph K3,2.
Figure 8c.22.
With the addition of F-diagrams, we have enough information to illustrate the smallest given graphs for all cyclic groups. The proofs of minimality can be found in Arlinghaus (1985).
Figure 8c.23 illustrates the graph for cyclic groups of order a prime p ≥ 7.
Figure 8c.23.
Thus α(p) = 2p if p ≥ 7 (notice the improvement from α(p) = 3p for p = 3,5).
Some fairly simple extensions of Figures 8c.21 and 8c.23 give the graphs for Zn, when n is a power of a prime p ≠ 2 (Figure 8c.24).
Figure 8c.24. a) left: p = 3,5 b) right: p ≥ 7.
Finally, if n=2a, a > 1, then the graphs of Figure 8c.25 give the minimal graph with group Zn.
Figure 8c.25. a) left: a = 2 b) right: a>2.
Combining these results gives the following theorem:
Theorem 8c.8 (Meriwether's Theorem). Let α(n) be shorthand for α(Zn). Then
α(2) = 2
α(2n) = 2n+6 if n ≥ 2
α(3n) = 3n+6
α(5n) = 5n+10
α(pn) = pn+p if p is a prime ≥ 7.
Sabidussi thought that it would be sufficient, by the Fundamental Theorem of Abelian Groups, to know α(Zn) for n a prime power. He conjectured, for instance, that if n=paqb, then α(n)= α(pa)+ α(qb). His idea was like that of Figure 8c.18, joining two components, one with group α(pa) and the other with group α(pb).
However, there is a series of exceptions. Sabidussi's expectations would be that α(180) = α(9)+ α(4)+ α(5)=15+10+15=40. But in fact α(180)=36 (Figure 8c.26).
Figure 8c.26.
This is like the first part of Figure 8c.24 with p = 3, n = 2; p in the leftmost circle replaced by 5p; and p in the rightmost circle replaced by 4p(1). A similar four-node savings occurs whenever n = 20 ⋅ 3a and a ≥ 1.
There are three other classes of exceptions, where nodes can be reduced from Sabidussi's conjecture
Since these are the only exceptions, α(n) can be determined for any n. Meriwether was aware of these exceptions, yet he felt that the Fundamental Theorem of Abelian Groups would carry the results forward. Therefore, he must have thought that no other exceptions could occur in the abelian case.
There are many new exceptions. For example, α(Z3a x Z3 x Z3) = 3a+18 if a ≥ 2. So in fact, six nodes can be eliminated. There are in fact eight classes of exceptions (Arlinghaus 1985, p. 66). This fact makes the statement of the calculation of α(A), A abelian, quite complex.
The general ideas, however, are rooted in the smallest graphs for n a prime power. Here graphs help to illustrate groups in a geometric setting.
The problem of finding a directed graph with given automorphism group is somewhat simpler, since the n-gon with n edges all oriented in the same way to create a directed circuit has automorphism group Zn (Figure 8c.27).
Figure 8c.27. a) left: digraph with group Z3 b) right: digraph with group Z4.
Let d(G) be the smallest number of nodes possible in a digraph with automorphism group G. Then clearly d(Z12) = 7 (the digraph of Figure 8c.27 has group Z12). The principles are the same as for graphs, but the details are easier. In fact, if A is an abelian group, and A has been written as a product of cyclic groups of prime power order, d(A) is the sum of those prime powers. For a complete discussion of the situation for directed graphs, see Arlinghaus and Harary (1987).
There is one final way in which graphs and their automorphisms illuminate a group theory concept, one that is often difficult to grasp.
Definition. Let A be a group of order m consisting of permutations of the set X = {x1, ..., xd }. Let B be a group of order n consisting of permutations of the set Y = {y1, ..., ye}. Define the wreath product A[B] to consist of the following mnd permutations of X x Y. If α ε A and β1, β2, ...βd are in B the permutation p = (α;β1,β2,...,βd) is defined as follows: if (xi,yj)ε X x Y, (xi,yj)p = (xiα, yjβj).
While this may seem somewhat obscure, consider Figure 8c.28. The graph exhibited there has three components, each of which has automorphism group Z3 (the B of our definition).
Figure 8c.28.
But an automorphism of this graph not only can move a node within a component, it can also permute the components arbitrarily (the permutations of components form a group isomorphic to S3 (the A of our definition). Thus, to find out what an automorphism does to a node, first determine which component it is in (x1, x2, or x3), then determine which component it is moved to by the automorphism (xiα), and then determine how the automorphism is permuting elements in that component (yjβj).
Thus the graph of Figure 8c.28 has automorphism group S3[Z3] with 6 ⋅ 33=162 elements. Indeed, if G is a graph with automorphism group A, then the graph consisting of n copies of G has automorphism group Sn[A]. Figure 8c.29 provides, without proof, three graphs with different wreath product groups as automorphism groups. Note that the last graph is a mixed graph, with both directed and undirected edges.
Figure 8c.29. a) left: group S4[Z2] b) center: group D4[Z2] c) right: group Z4[Z2]
Graphs provide geometric representatives that make groups easier to understand. It is our hope that graph theory will illuminate a variety of applications as another tool in the researcher's kit.