MATHEMATICA MONTISNIGRI Vol XXI XXXI (2014) Vol (2014) AUTOMORPHISM GROUPS OF SOME CLASSES OF GRAPHS DUŠAN S. JOKANOVIĆ* AND MARINA M. ZIROJEVIĆ† * University of East Sarajevo Production and Management Faculty Trebinje Stepe Stepanovića bb, 89 101 Trebinje, Republic of Srpska, BiH e-mail: [email protected], web page: http://www.fpmtrebinje.com † University of East Sarajevo Production and Management Faculty Trebinje Stepe Stepanovića bb, 89 101 Trebinje, Republic of Srpska, BiH e-mail: [email protected], web page: http://www.fpmtrebinje.com Summary. There is a natural connection between the fields of algebra and graph theory. Both provide interesting ways of studing relationships among elements of a given set. An algebraic approach to graph theory can be useful in numerous ways. These arise from two algebraic objects associated with a graph: its adjacency matrix and its automorphism group. In this paper we investigate automorphism groups of common graphs and introduce a celebrated theorem of Sabidussi. Beside, by finding a graph of a given group, we can define an extremely important family of vertex-transitive graphs. The paper discusses algebraic aspects of Cayley graphs and its group of automorphism. We also give a short presentation of tools which are developed in “Wolfram Mathematica 10.0.” to represent finite groups, to perform various group operations. 1 INTRODUCTION The automorphism group of graph can be naturally defined as a group of permutations of its vertices, and so presents some basic information about permutation group. A permutation of a set Ω is a bijective mapping p : W W . The composition p1p2 of two permutation p1 and p2 is the permutation obtained by applying p1 and then p2 , thus is: v (p1p2 ) = ( vp1 ) p2 for each v Î W . (1) A permutation group on W is a set S of permutations of W satisfying the following conditions: S is closed under composition: if p1 , p2 Î S than p1p2 Î S ; S contains the identity permautation 1 defined by v1 = v for v Î W . S is closed under inversion, where the inverse of p is the permutation p-1 defined by the rule that vp-1 = w if wp = v . In this paper Sym(W) denotes the set of all permutations of W , Sn denotes the symmetric group Sym ({1, 2, , n }) . Let S be a permutation group on W . The relation on W , defined by v w if w = vp for some p Î S , 2010 Mathematics Subject Classification: 11H56, 00А00, 18A10, 00B00, 00C00. 68R10. Key words and Phrases: Automorphism groups of graphs, Cayley graphs. 16 (2) DUŠAN S. JOKANOVIĆ M. ZIROJEVIĆ Dušan S. Jokanović, AND MarinaMARINA M. Zirojević is an equivalence relation, and its equivalence classes are the orbits of S. S is transitive if it has just one orbit, thus, S is transitive if, for any v, w Î W there exists p Î W such that vp = w . The stabilizer Sv of a point v Î W is the set (3) H = {p Î S : vp = v} ; it is a subgroup of S. Moreover, if w is a point in the same orbit as v, then the set {p Î S : vp = w } (4) is a right coset of H in S. 2 AUTOMORPHISMS OF TYPICAL GRAPHS Let : V , E be a simple, undirected graph. An automorphism of a graph is a permutation of the vertex set that preserves adjacency. The set of all automorphisms of a graph , with the operation of composition of permutations, is a permutation group on vertex set that preserve adjacency. This is the automorphism group of graph denoted by (5) A() : Sym V : ( E ) E . The automorphism group is an algebraic invariant of a graph. Here are some simple properties (see [1]). Theorem 1. (a) A graph and its complement have the same automorphism group. (b) The automorphism group of n disjoint copies of graph is A(n) Sn A . (c) A K n Sn . Every graph has the trivial automorphism id : V V defined by id (v ) v . Most graphs have no other automorphisms than, but many interesting graphs have many automorphisms. Erdös and Rényi [3] showed: Theorem 2. Almost all graphs have no non-trivial automorphisms. The smallest graph, apart from the one-vertex graph, whose automorphism group is trivial is shown in Figure 1. Figure 1: A graph G for which A (G) = 1 Cyclic graph C4 is the opposite case, because it has 8 automorphisms. In order to define the possible automorphisms of C4 , we will define Z 4 : 1, 2, 3, 4 . First, v1 vi for 17 DUŠAN S.Dušan JOKANOVIĆ AND MARINA M. ZIROJEVIĆ S. Jokanović, Marina M. Zirojević some i Z 4 . Then v2 has to be a neighbour of vi , so it is either vi 1 or vi 1 . Now v4 has to be the neighbour of vi that isn’t v2 , so it is vi 1 or vi 1 , whichever one is not v2 . Finally, vi 2 is the only remaining vertex not yet in the image of , so it must be equal to v2 . We had 4 choices for i , and then we had to choose either i + 1 or i -1 , which is 2 further choices. That gives us 4´ 2 = 8 ways to choose an automorphism of C4 ; thus A(C4 ) = 8 . Example 1. Let G be the octahedron graph. The octahedron graph are shown on next Figure. The complement graph of the octahedron graph is 3K 2 . We can easily calculate that A(3K 2 ) = 233! = 48 since there are 3! ways to permute edges and on each edge we can either switch vertices on that edge or leave them fixed what yields another 23 automorphisms. Because every automorphism preserves adjacency as well as non-adjacency, a graph and its complement have the same automorphism group, so we have A(G) = 233! = 48 . Figure 2: The Octahedron graph Graph which has more automorphism than any other graph, relative to its size is Petersen graph P. Let Z5 = {1, 2,3, 4,5} and let P2 ( Z5 ) be the set of all unordered pairs of elements of Z5 . Then V (P) = {vij : {i, j} Î P2 ( Z5 )} . The vertices v ji and vij are the same vertex. Two vertices in P are adjacent if and only if their labels are disjoint sets, ie E(P) = {vij v ji : {i, j} Ç {k, l} = Æ} . The Petersen graph with the 2-index vertex labelling are shown on the next Figure. 18 DUŠANDušan S. JOKANOVIĆ AND MARINA M. ZIROJEVIĆ S. Jokanović, Marina M. Zirojević Figure 2: The Petersen graph Any permutation of Z5 gives an automorphism of P, and different permutations give different automorphisms. Because there are no other automorphisms of P we can say A (P) = 120 . Following results holds: Theorem 3. The full automorphism group of the Petersen graph is isomorphic to S5 . Proof: Let G be the Petersen graph. Every element p Î S5 induces a permuatation p of G . Each of these permutations is an automorphism of G because for all p Î S5 , A, B are disjoint if and only if p (A) and p (B) are disjoint. Thus, the map f : S V, p p is an injective 5 group homomorphism into A (G) , and so S5 @ f (S5 ) £ A (G) . If we want to show that there is no other automorphisms than f (S5 ) i.e. that f (S5 ) is a full automorphism group, it is sufficed to show that A (G) £ f (S5 ) . If p is any automorphism, then by composing with an appropriate permutation of {1,2,3,4,5} we may assume that the map fixes {1,2}; that means that the vertices adjacent to {1,2}, {3,4}, {3,5}, and {4,5}, must map to each other. To prove this, let p Î A (G) . We show that there exists -1 g Î f (S5 ) such that p g = 1 . This would imply that p = g Î f (S5 ) . g1 fixes the vertex 12 Suppose p : {1, 2} {a, b} . Let g1 Î S5 map a 1 , b 2 . Then p and hence permutes its neighbors 34, 45 and 35. We consider a few cases: g1 fixes all three neighbors 34,45,35. So p g1 permutes the neighbors of 35, and 1. Suppose p hence fixes 14 and 24, or swaps 14 and 24. 19 DUŠANDušan S. JOKANOVIĆ MARINA M. ZIROJEVIĆ S. Jokanović,AND Marina M. Zirojević 1.1. If p g1 :14 14 , then 15 is sent to a vertex adjanced to 34 and not adjanced to 14, hence 15 is fixed. Similary, all the vertex are seen to be fixed, and so p g = 1 , as was 1 to be shown. g1 :14 24 , then it swaps 14 and 24. 15 is sent to a neighbor of 24( p g1 )=14, and 1.2. If p hence 15 is sent to 25. Thus, we see that pg swaps 14 and 24, 15 and 25, and also 13 1 and 23, and fixes the remaining vertices. But then p g1 = g 2 , where g 2 = (1, 2) . So, p Î f (S5 ) . 2. Suppose p g1 fixes exactly 2 of the 3 vertices 34, 45 and 35. But this case is not possible, because if it fixes 2 of the 3 vertices, it must also fix the third vertex. g1 fixes exactly 1 of 34, 45 and 35, say 34. So p g1 swaps 45 and 35. Let p g1 3. Suppose p swaps 45 and 35. Let g = (3, 4) . Then p g g satisfies the condition of case (1). 2 1 2 4. Suppose p g1 fixes none of 34, 45 and 35. Say it has (34, 45, 35) as a 3-cycle. Let g = (3, 4) . Then p g g = (34,35)(45) , and we are back to case (3). 2 1 2 In all cases if p Î Aut (G) , then for some nonnegative integer r, there exists g1 , , g r such that pg1 , , g r = 1 , implying that p Î f (S5 ) . □ 3 VERTEX-TRANSITIVE GRAPHS A graph G is vertex-transitive if the automorphism group of G acts transitively on the vertex-set of G . Thus for any two distinct vertices of G there is an automorphism mapping one to other. Common example of vertex-transitive graphs is k-cubes Q k . The vertex-set of Q k is the set of all 2k binary k-tules, with two being adjacent if they differ in precisely one coordinate position. Theorem 4. The k-cone Q k is vertex-transitive. Proof. If we fixed k-tuple, then the mapping r v : x x + v is a permutation of the vertices of Q k . This mapping is an automorphism bacause the k-tuples x and y differ in precisely one coordinate position if and only if x+v and y+v differ in precisely one coordinate position. There are 2k such permutations, and they form a subgroup H of the automorhism group of Q k . This subgroup acts transitively on V (Q k ) bacause for any two vertices x and y, the automorhism r y-x maps x to y. □ Another example of vertex-transitive graph are circulant graphs. Definition 1. Let n denote the additive group of integers modulo n. If C is a subset of n \ 0 , then construct a direct graph G ( n , C) as follows. The vertices of G are the elements 20 DUŠAN Dušan S. JOKANOVIĆ AND MARINA M. ZIROJEVIĆ S. Jokanović, Marina M. Zirojević of n and (i,j) is an arc of G if and only if j - i Î C . The graph G ( n , C) is called a circulant graph of order n, and C is called its connection set. The cycles are special cases of circulant grahs. The cycle Cn is a circulant graph of order n, with conection set {1, -1} . The complete and empty graphs are also circulant, with connection set C = n and C = 0 , respectively. Let G be a group and let C be a subset of G that is closed under taking inverses and does not contain the identity. Then the Cayley graph G (G, C) is the graph with vertex set G and edge set E (G (G, C)) = {gh : hg-1 Î C} . (6) Theorem 5. The Cayley graph G (G, C) is vertex transitive. Proof. For each g Î G the mapping r g : x xg (7) is a permuatation of the elements of G. This is an automorphism of G (G, C) because -1 ( yg)( xg ) = ygg-1x-1 = yx-1 , (8) and so xg yg if and only if x y . The permutations r g form a subgroup of the automorphism group of G (G, C) isometric to G. This subgroup acts transitively on the vertices of G (G, C) because for any two vertices g and h, the automorphism r g-1h maps g to h. 4 CAYLEY GRAPHS As we mentioned before, every Cayley graph is vertex-transitive. In fact, most small vertex transitive graphs are Cayley graphs, but there are also many families of vertex transitive graphs that are not Cayley graphs. One example of such graph is Petersen graph. He is vertex-transitive, but not Cayley graph. Circulant graph on n vertices is a Cayley graph for the cyclic group of order n and k-cube is a Cayley graph for the elementary abelian group k2 . Some Cayley grahs appear frequently in the literature. The complete graphs and their complements are Cayley graphs. K n is a Cayley graph on any group G or order n where connection set is the set of non-identity elements of the group. The graph formed on the finite field q , where q = 1(mod 4) and the connection set is the set od quadratic residues in q , is also a Cayley graph, called a Paley graph. Definition 2. Let p be a prime number and n be a positive integer such that p n º 1(mod 4) . The graph P = (V, E ) with 21 S. Jokanović, Marina M. Zirojević DUŠAN Dušan S. JOKANOVIĆ AND MARINA M. ZIROJEVIĆ ( )} { V (P) = pn and E (P) = {x, y} : x, y Î pn , x - y Î p*n 2 (10) is called a Paley graph. The list of integers which can be considered as an order of the Paley graph starts with 5, 9, 13, 17, 25, 29, 37, 41, 49, 53, 61, 73, 81… . The Paley graph of oreder 5 is cycle C5 . Answer to question whether the arbitrary graph is a Cayley graph gives the theorem of Sabidussi. Before the proceeding to the theorem, a definition is required. Let G be a transitive permutation group acting on a finite set Ω. Folowing three conditions are equivalent: 1. The only element of G that fixes an element of Ω is the identity permutation; 2. G = W ; 3. For any w1 , w 2 Î W , there is a unique element p Î G satisfying w1p = w 2 . A transitive permutation group G that satisfies any of the these conditions is said to be regular. We now state the theorem of Sabidussi. Theorem 6. A graph Г is a Cayley graph if and only if A(Г) contains a regular subgroup. Some of the most interesting and extensively investigated problem connected with Cayley graph is trying to determine when two graphs are isomorphic. Let p be a prime and let *p denote the multiplicative group of units of p . Define the permutation Ta,b on p for a Î *p and b Î p , by xTa,b = ax + b . Denoting equivalent permutation group as G º H , we state theorem of Burnside. Theorem 7. A transitive permutation group G of prime degree p is either doubly transitive or G º {Ta,b : a Î H < *p , b Î p } . Burnside’s theorem has applications for circulant graphs of prime order. If A (G) is doubly transitive for a graph G , then G is either complete or has no edges. The most important result about isomorphism of Cayley graph is provided by theorem of Turner via next characterization. Theorem 8. Let p be a prime. Two circulant graphs G (p, C) and G (p, C ') of order p are isomorphic if and only if C ' = aC for some a Î *p . It is very difficult to determine the full automorphism group of Cayley graphs. The answer is complete known in special case od prime order circulants. Suppose that p is a prime, and that we are given the circulant graph G (p, C) , which is Cayley graph on the additive group p . The graph is complete if and only if C is all of *p and it is empty graph if and only if C is Æ . The resulting automorphism group is symmetric group Sp . When Æ Ì C Ì *p using Theorem 7 we obtain that A (G) has the form {Ta,b : a Î H < *p , b Î p } . This implies that the stabilizer of the vertex labelled 0 is Ta,0 with a Î H < p . Thus, if there is an edge joining 0 and k in G , than there is an edge joining 0 and all of kH , and so the connection set C is a union of cosets of the multiplicative subgroup H of 22 S. Jokanović,AND Marina M. Zirojević DUŠANDušan S. JOKANOVIĆ MARINA M. ZIROJEVIĆ *p . If C is a union of cosets of the subgroup H of *p , but not an union of cosets of any supergroup of H, then the stabilizer of 0 is {Ta,0 : a Î H < *p } and we know precisely what A (G) is. If graph G is a circulant graph G (p, C) and Æ Ì C Ì *p , then let e (C) denote the maximum even order subgroup H of *p for which C is an union of cosets of H. We now state the folowing result. Theorem 9. Let graph G be a circulant graph G (p, C) of prime order. If C = Æ or *p , then A (G) = Sp . Otherwise, A (G) = {Ta,b : a Î e (C) , b Î p } . 5 APLICATION OF “WOLFRAM MATHEMATICA 10.0” IN ALGEBRAIC GRAPH THEORY In closing section we investigate „Wolfram Mathematica 10.0“ which contains many constructors and tools relating to group theory and algebraic graph theory. The automorphisms group of graph Г may be computed in Mathematica using GraphAutomorphismGroup[g]. Precomputed automorphisms for many named graphs can be obtained using GraphData[graph, "Automorphisms"]. Just a small part of Wolfram Mathematica utility and his package Combinatorica will be exemplified by the following example. The example shows graph constracting in Wolfram Mathematica, finding his group of automorphisms, group generating set, group orbits and Cayley graph. Example 2. 23 S. Jokanović, Marina M. Zirojević DUŠAN S.Dušan JOKANOVIĆ AND MARINA M. ZIROJEVIĆ Acknowledgements: This research was supported under the grant by the Ministry of Science and Technology, Government of the Republic of Srpska. REFERENCES [1] L. Beineke, R. Wilson and P. Cameron, Topics in Algebraic Graph Theory,Cambridge University Press, (2004). [2] C. Godsil and G. Royle, Algebraic Graph Theory, Springer-Verlag New York, (2001). [3] P. Erdős and A. Rényi, Asymmetric graphs, Acta Math. Acad. Sci. Hungar, (1963). [4] G. H. Fath-Tabar, The automorphism group of finite graphs, Iranian Journal of Mathematical Sciences and Informatics Vol.2, No.2 (2007). [5] R. Jajcay, The Structure of Automorphism Groups of Cayley Graphs and Maps, Journal of Algebraic Combinatorics 12 (2000). [6] A. N. Elsawy, Paley Graphs and Their Generalizations, A thesis submitted to Heinrich Heine University Düsseldorf, Germany for the Degree of Master of Science, (2009). Received March, 20 2014 24

© Copyright 2017 ExploreDoc