A Study of Theory on Algebra Graphs on Group D2n, Sn and An Group

INTRODUCTION

The algebra has three historical stages in many texts: the rhetorical stage, the syncopated stage and the symbolic stage. By rhetoric we mean the stage in which all statements and arguments are expressed in words and phrases. Some abbreviations are used for algebraic expressions in the syncopated stage. And finally there is complete symbolized on the symbolic stage – every number, operation, relationship is expressed through a number of easily recognized symbols and symbol manipulations are carried out by well-understood rules. The three stages are definitely one way to look at algebra history. The conceptual phases are the geometry phase, in which most algebra concepts are geometric, a static equation resolution stage, in which the aim is to find figures that satisfy certain relationships, the dynamic function phase, in which motion is an underlying idea. Of course, not one of these or the previous three stages is united; there is always some overlap. The term algebraic reasoning was used to describe mathematical processes that generate problems with different representation patterns and models. Comprehension is an abstract thought expressing logical power. Piaget suggested that understanding in general and especially in mathematics is a highly complex abstraction process. Conceptual understanding in algebra can be characterized as the ability to recognize and to distinguish and interpreted between functional relationships between known and unknown, independent and dependent variables. The ability to read, write and manipulate both numerical symbols and algebraic symbols in formulas, terms, equations and inequalities is evident. Algebra fluences are also indicative of conceptual understanding in algebra through the confident use of vocabulary and meanings, and by flexible application of its grammar (i.e. mathematical qualities and conventions). We begin with a short review of some of the basic concepts of graph theory and group theory. One of the most widely known and extensively studied family of vertex transitive graphs is the family of Cayley graphs. The construction of Cayley graphs is depend upon on groups. We restrict are attention only to finite groups. Let G denote an abstract group and let S ⊆ G such that 1G ∈/ S. The Cayley graph of G relative to S is

directed graph, but if S = S −1 we will obtain an undirected Cayley graph. The edges of Γ represent the orbits of unordered pairs of elements of G under the action of S. If hSi is a proper subgroup of G and g ∈ G, g /∈ hSi, then the vertices 1G, g ∈ V (Γ(G, S)) = G belong to different components of the graph and therefore the graph is not connected. We can observe that S generates the whole group G if and only if the corresponding Cayley graph is connected (or in other words, S generates G if and only if there is path which connects any two vertices of V (Γ(G, S)) = G). It easily follows that Cay(G, S) has valency |S| . Example 1 The Cayley graph Γ(S3, {(12),(123),(132)}). Example 2 Let G be a finite group. Let H be a subgroup of G, and define the set S to be the subgroup H with the identity removed. Let gh be an edge of Γ(G, S), then gh−1 is an element of S, and hence is an element of H, which implies that the cosets Hg and Hh are equal. Thus Γ(G, S) is a graph depicting the cosets of H in G, where two vertices are adjacent if and only if they are in the same coset thus there are |G : H| components. Lemma 1. Let G be a finite group. The Cayley graph Γ(G, S) is a connected graph if and only if S ⊆ G is a generating set for G. Example 4 Three Cayley graphs Γ(G, S) of the dihedral group G = D8. The first two graphs are examples of a Cayley graph depicting the cosets of D8 for the subgroups hbi and hai respectively (where S is the subgroup minus the identity in each case). In the final graph, S = {a, b, b3} is a generating set for D8. Observe that this graph is connected.

In this section we determine the number of Cayley graphs on a dihedral group D2n that are undirected. The complement S¯ of Cayley subset S with respect to G\{1G} is also a Cayley subset. Because if x ∈ S¯ then x /∈ S and since S is a Cayley subset x −1 ∈/ S. adjacent in Γ =¯ Cay(G, S¯) if and only if they are not adjacent in Γ = Cay(G, S). So the automorphism group of Γ = Cay(G, S) is equal to the automorphism group of Γ =¯ Cay(G, S¯). Recently Gholamreza Aghababaei Beny and Zarullo Rakhmonov [14] have derived a formula for number of Cayley groups on Zn that are undirected. Theorem 1 Let G be a finite group. Number of Cayley graphs undirected and contrasting with group of Zn are: i) If n = 1, then nonexist the undirected Cayley graph for group Zn. ii) If n = 2 or 3, then number of Cayley graph that undirected is one. iii) If n ≥ 4 and n is even then number of Cayley graph that undirected is iv) If n ≥ 4 and n is odd then number of Cayley graphs that are undirected is Theorem 2 . Suppose |Sk| denotes the number of Cayley graphs Γ = Cay(D2n, S) with |S| = k and n odd. Then Here denotes the greatest integer ≤ x. Proof. Suppose n is odd. Then where The orders of the elements in the set A is 2. Hence for every element of A its inverse is itself. If is an arbitrary element of . So, its inverse is If S is a Cayley subset of D2n with k elements, then if and only if . Since we have such pairs in A¯, we can construct a Cayley subset with k elements by choosing m () pairs of elements of A. This implies that the number of Cayley graphs that undirected and having k elements is As the proof of the following theorem is similar to that of Theorem 2.2.2 we omit the proof. Theorem 3 Let |Sk| be the number of Cayley graphs Γ = Cay(D2n, S) with |S| = k and n even. Then Theorem 4 Let N(D2n) denotes the number of Cayley graphs on a Dihedral group D2n. Then Proof. If S is a Cayley subset of D2n with k elements (1 ≤ k ≤ n−1), then its complement S¯ with respect to D2n\{1} is also a Cayley subset of D2n with (2n − 1 − k) elements. Thus |Sk| = |S2n−1−k|, 1 ≤ k ≤ n − 1. Suppose n is odd. Then, we have Theorem 5 Let N(D2n)denotes the number of Cayley graphs on a Dihedral group D2n. Then Proof. Case (i) n-odd. If S is a Cayley subset of D2n and b i ∈ S, 0 < i ≤ n − 1 if and only if b n−i ∈ S. Also note that inverse of abi , 0 ≤ i ≤ n−1 is itself. Hence N(D2n) is the number of nonempty subsets of a set Remark 6 Combining Theorem 4 and Theorem 5 we have the following beautiful identities:

In this section we investigate some properties of the Cayley graphs Γ on a symmetric group Sn. A permutation of a set Ω is a bijection α : Ω → Ω. If Ω is a finite set and | Ω |= n, then an arrangement of Ω is a list x1, x2, ..., xn with no repetitions of all the elements of Ω. The family of all the permutations of a set Ω, denoted by SΩ, is called the symmetric group on Ω. When Ω = {1, 2, ..., n} , SΩ is usually denoted by Sn, and it is called the symmetric group on n letters. If α ∈ Sn and i ∈ {1, 2, ..., n}, then α fixes i if α(i) = i, and a moves i if Let i1, i2, ..., ir be distinct integers in {1, 2, ..., n}. If α ∈ Sn fixes the other integers (if any) and if then α is called an r-cycle. One also says that α is a cycle of length r. A 2-cycle interchanges i1 and i2 and fixes everything else; 2-cycles are also called transpositions. A 1-cycle is the identity, for it fixes every i; thus, all l-cycles are equal: (i) = (1) for all i. We now introduce new notation: an r-cycle α, as in the definition, shall be denoted by . Two permutations α are disjoint if every i moved by one is fixed by the other: if of permutations is disjoint if each pair of them is disjoint. Disjoint permutations commute. Every permutation is either a cycle or a product of disjoint cycles. Every permutation is a product of 2-cycles. We shall refer to 2-cycles as transpositions. A permutation is said to be an even permutation if it can be represented as a product of an even number of transpositions. We call a permutation odd if it is not an even permutation. Sn has as a normal subgroup of index 2 the Alternating group, an, consisting; of all even permutations. More details about Symmetric groups. Now we proceed towards some theorems about the number of Cayley graphs.

and denotes the greatest integer ≤ x. Proof. Suppose . Then where are Since in the symmetric group every k-cycle has order k, and if σ is k-cycle and τ is an is a l-cycle and these two cycles are disjoint then and this element has order lcm(k, l). Therefore all of elements in A has order 2. Hence for every element of A its inverse is itself. Also if there are And if kr ≤ n, where , then the number of , where ρ is a product of k disjoint where we denotes |A| by γ(Sn). If S is a Cayley subset of Sn with k elements, ρ ∈ S if and only if ρ −1 ∈ S. Since we have b n!−1−γ(Sn) 2 c such pairs in A¯, we can construct a Cayley subset with k elements by choosing m ( elements of A. This implies that the number of Cayley graphs that undirected and having k elements is Theorem 2.3.2 Let N(Sn) denotes the number of Cayley graphs on a symmetric group Sn. Then Proof. If S is a Cayley subset of Sn with k elements (0 ≤ k ≤ n! − 1), then its complement S¯ with respect to S ∗ n = Sn\{1Sn } is also a Cayley subset of Sn with (n! − 1 − k) elements. Thus |Sk| = |Sn!−1−k|, Theorem 2.3.3 Suppose |Sk| denotes the number of Cayley graphs Γ = Cay(An, S) with |S| = k. Then Proof. Suppose Then where A = are disjoint, 2-cycle and the number of those are even, . We note that An ≤ Sn and in the symmetric group Sn, every k-cycle has order k, and if σ is k-cycle and τ is an is a l-cycle and these two cycles are disjoint then στ = τ σ and this element has order lcm(k, l). Therefore all of elements in A has order 2. Hence for every element of A its inverse is itself. If kr ≤ n, where 1 < r ≤ n, then the number of ρ ∈ Sn, where ρ is a product of k disjoint is even then where we denotes If S is a Cayley subset of An with k elements, ρ ∈ S if and only if Since we have such pairs in A¯, we can construct a Cayley subset with k elements by choosing pairs of A¯ and k − 2m elements of A. This implies that the number of Cayley graphs that undirected and having k elements is Theorem 2.3.4 Let N(An) denotes the number of Cayley graphs on a Alternating group An. Then

A fundamental problem in graph theory is the so-called isomorphism problem, that is, to decide whether two given graphs are isomorphic or not. In this section we investigate the isomorphism problem for finite Cayley graphs on symmetric group Sn. The following Theorems are basic for Cayley graphs and Cayley subsets. Theorem 2.4.1 [41] Let Sn be Symmetric group and n > 2 then Aut(Sn) = Sn except when n = 6. In the exceptional case . is an arbitrary automorphism of Symmetric group Sn, then it can be expressed by Theorem 2.4.2 [46]If α is an automorphism of group G, then Cay(G, S) and Cay(G, α(S)) are isomorphic. The converse of the Theorem 2.4.2 is not true. Two Cayley graphs for a group G can be isomorphic even if there is no automorphism of G relating their connection sets. The converse of Theorem 2.4.2 about Cayley Graphs of Alternating group A4 and all disconnected Cayley graphs of A5 [51] and all Cayley graphs of A5 of valency 4 is true [70] which was a conjecture posed by Li and Praegar [62]. number of non-isomorphic Cayley graphs of symmetric group Sn and Alternating group An for n = 3, 4. First we prove two lemmas which are necessary to prove our results. Lemma 2.4.4 Let Sn(n ≥ 4) be Symmetric group. Then Cay(Sn, {(12),(13)}), Cay(Sn, {(12),(34)}), Cay(Sn, {(12),(13)(24)}) Cay(Sn, {(123),(132)}) are all Non-Isomorphic to each other. i.e up to isomorphism, there are at least 4 Cayley graph on Symmetric group Sn of valency 2. Proof. Let H = h(12),(13)i be a subgroup of Sn. Let gh be an edge of Cay(Sn, {(12),(13)}), then gh−1 is an element of H\{1Sn }, which implies that cosets Hg and Hh are equal. So two vertices are adjacent if and only if they are in the some coset. Thus there are |Sn : H| components; each of which is a clique of size |H|. But This implies that Cayley graphs of Sn of valency 2 as above are all nonisomorphic to each other.

CONCLUSION

Moreover it is shown that any non-commuting elements remains non adjacent in cyclic graph. It can be said cyclic graph lies in between power graph and commuting graph. That is if power graph, cyclic graph and commuting graph are constructed from same finite group then power graph is a sub graph of cyclic graph and cyclic graph is a sub graph of commuting graph. It is found in a cyclic graph maximum degree is always attainable. It is also shown that whatever the finite group is, cyclic graph is always connected. It‘s

remaining graphs it still remains an interesting open problem. Remaining two algebraic graphs are constructed from finite rings. For any finite ring and a polynomial with coefficients from the ring a polynomial graph is constructed. In this algebraic graph vertices are the elements of the finite ring and two vertices are adjacent if one is the image of the other under the polynomial. Some properties of the polynomial graph such as degree of vertices, maximum degree cardinality of edges are studied. Moreover for some fixed polynomials the obtained graph structure is determined completely. The maximum degree of the polynomial graph in a finite field is at most one more than the degree of the polynomial. In polynomial family graph a family of polynomial is used instead of a single polynomial. This algebraic graph is constructed from finite ring and the edges are constructed from family of polynomials. That is, a graph is constructed from a family of polynomials in a finite ring. In this graph the ring elements are the vertices. The obtained new graph is denoted by polynomial family graph generated by that family. Whenever an element is the image of the other with respect to some polynomial in the family both the elements are made adjacent. Few parameters in polynomial family graph of a finite ring such as edge domination number, vertex domination number, independence number, chromatic number and matching number are studied. Here the vertex domination number is found in two different ways. The concepts polynomial graphs and polynomial family graphs can be further developed in a lot of ways. The study of algebraic structures, using the properties of graphs, becomes an exciting research topic in the last twenty years, leading to many fascinating results and questions. There are many papers on assigning a graph to a ring or group and investigation of algebraic properties of ring or group using the associated graph. In short a wonderful world of algebraic graph theory is open for further analysis.

REFERENCES

[1] N. L.Biggs, R. Lloyd and R. Wilson (1986). Graph theory 1736-1936, Clarendon Press. [2] B. Bollobas (1979). Graph theory: An introductory course New York: Springer-Verlag. [3] B. Bollobas (1979). Modren graph theory, New York: Springer-Verlag. [4] B. Bollobas (1998). Modern graph theory New York: Springer-Verlag. [5] J. A. Bondy and U.S.R. Murty (1976). Graph Theory with applications American Elsevier Publishing Co., Inc New York. [7] A. E. Brouwer, and W. H. Haemers (2011). Spectra of Graphs, Springer. [8] R. A. Buraldi (2006). Energy of a graph, Notes for AIM Workshop On Spectra of families of matrices described by graphs, digraphs, and sign patterns. [9] R. A. Buraldi and A. J. Hoffman (1985). On the spectral radius of (0,1)- matrices, Linear Algebra Appl., 65, pp. 133-46. [10] D. de Caen (1998). An upper bound on the sum of squares of degrees in a graph, Discrete Math., 185, pp. 245-248. [11] C. K. Caldwell: Graph theory tutorials http:// www. utm. edu/ departments/ math/ graph/. [12] A. Cayley (1857). On the theory of the Analytical forms called trees. Phil.mag.(4) 13, pp. 172-176. [13] A. Cayley (1859). On the theory of the Analytical forms called trees. Phil.mag.(4) 18, pp. 374-378. [14] G. Chartrand (1985). A scheduling problem: Introductory graph theory New York, Dover. [15] F. R. K. Chung (1995). Eigenvalues of graphs, in: Proceeding of the International Congress of Mathematicians, Z¨urich, Switzerland, pp. 1333-1342. [16] L. Collatz and U. Sinogowitz (1957). Spektren endlicher Grafen, Abh. Math. Sem. Univ. Hamburg, 21, pp. 63-77. [17] C. A. Coulson, B. OLeary, R. B. Mallion (1978). Huckel Theory for Organic Chemists Academic Press, London. [18] D. Cvetkovic, M. Doob, H. Sachs (1995). Spectra of graphs. Theory and application, third ed., Johann Ambrosius Barth Verlag, Heidelberg, Leipzig.

PhD Student, Kalinga University, Raipur