Pure and Applied Mathematics Journal
Volume 4, Issue 3, June 2015, Pages: 128-132

Enumeration of Triangles in Cayley Graphs

1Department of Applied Mathematics, Yogi Vemana University, Kadapa, A. P., India

2Department of Mathematics, Sree Vidyanikethan Engineering College, A. Rangampet, Tirupati, A. P., India

(T. Chalapathi)

Levaku Madhavi, Tekuri Chalapathi. Enumeration of Triangles in Cayley Graphs. Pure and Applied Mathematics Journal. Vol. 4, No. 3, 2015, pp. 128-132. doi: 10.11648/j.pamj.20150403.21

Abstract: Significant contributions can be found on the study of the cycle structure in graphs, particularly in Cayley graphs. Determination of Hamilton cycles and triangles, the longest and shortest cycles attracts special attention. In this paper an enumeration process for the determination of number of triangles in the Cayley graph associated with a group not necessarily abelian and a symmetric subset of the group.

Keywords: Cayley Graphs, Fundamental Triangle, Triangle and Group

1. Introduction

The cycle structure of Cayley graphs associated with certain arithmetic functions were studied by Berrizbeitia and Giudici[2][3] and Dejter and Giudici [5]. Maheswari and Madhavi [7] [8] enumerated Hamilton cycles and triangles in arithmetic Cayley graphs associated with Euler totient function and quadratic residues modulo a prime. The number of triangles in the arithmetic Cayley graph associated with the divisor function is determined in [4].

In [2] Berrizbeitia and Giudici consider sequences of Cayley graphs satisfying the multiplicative arithmetic property, where is a finite abelian group and is a subset of . The sequence of Cayley graphs  as the multiplicative arithmetic property (map) if for each pair of positive relatively prime integers there is a group isomorphism from  to  such thatmaps  onto . In [2], it is proved that if  is a sequence of Cayley graphs with the map, then that function  is a linear combination of multiplicative arithmetic functions, where  denotes that number of induced k-cycles of  using this formula the  and  are obtained for the sequence  in terms of prime divisors of , whereis the ring of integers modulo  and  is the multiplicative group of units modulo. In this paper we give a formula for determining the number of triangles in a Cayley graph  where  is a finite group, not necessarily abelian and  is a symmetric subset of.

2. Enumeration of Triangles in Cayley Graphs

Let  be a group. A subset  of  is called a symmetric subset if for all. The graph  with vertex set and edge set is called the Cayley graph of corresponding to the symmetric sub setof .We denote this graph byand assume that does not contain the identity element of  so that  contains no loops. Clearly  is an undirected graph which is - regular with size and vertex transitive.

associated with a group  not necessarily abelian, and a symmetric sub set  of .

Definition 2.1: Let  be the identity element of the group. For, if the triad  is a triangle in then  is called a fundamental triangle.

Lemma 2.2: For a given  the number of fundamental triangles in  is.

Proof: Let. For any, is a fundamental triangle and  are edges in ,    and .That is, for a given  and for each  the triad  is a fundamental triangle in  and vice versa so that the number of fundamental triangles in  is .

Lemma 2.3: The number of distinct fundamental triangles in  is .

Proof: By the Lemma 2.2, for each  the number of fundamental triangles in is so that the total number of fundamental triangles in  is.

However the triangles  and  represent the same fundamental triangle sinceis a symmetric subset of,

.

So the number of distinct fundamental triangles in  is

Theorem 2.4: The number of distinct triangles in  is

Proof: Let  be the identity element of the group and let  be any vertex of . Since  is vertex transitive and regular, the number of triangles in  with as one vertex is equal to the number of fundamental triangles in  namely,

and the number of triangles in is

However each triangle in  is counted thrice, namely, once by each of its three vertices so that the number of distinct triangles in  is

.

The following Corollary is immediate.

Corollary 2.5: The Cayley graph  has no triangles if and only if  for all.

Example2.6: For the Dihedral group and its symmetric subset

, where

,,,,,, and

consider the Cayley graph

Cayley Graph

Since, and we have, and . So the number of distinct triangles in

is equal to

and has no triangles .

Example 2.7: Consider the Cayley graph  where.

Cayley Graph

Since, and, we have , ,,  and . So the number of distinct triangles in  is equal to

.

3. Deductions

3.1. Enumeration of Triangles in the Euler Totient Cayley Graph

Let  be an integer and let  be the group of residue classes modulo  with respect to the addition  modulo. Then the set  and  is relatively prime to is a symmetric subset of . The Euler totient Cayley graph  is the graph whose vertex set is

and the edge set

.

In [8] it is established that the graph  is - regular with size, Hamiltonian, connected, bipartite and contains no triangles if  is even.

For any vertex  in ,,

and  belong to, or, they constitute a pair of consecutive integers less than  and relatively prime to.

Thus, the Schemmel totient function which denotes the number of pairs of consecutive positive integers less than  and relatively prime to. Further using the fact that  is a multiplicative subgroup of order of the semi-group, where, and denotes the multiplication modulo, one can see that for. To establish this, fordefine the map

by for all .

Let .Then  and  so thatand for some.Since  is a group,  implies that so that .

Hence themapsinto.

For, implies that. Since is a group, this gives  and  is one- to - one.

Let. Then and  for some.Since  is a group, for  there exist  such that so that

,

or, , since .

Also  implies that.That is, . For this  and .This shows that is onto and hence a bijection showing that.

So by the Theorem 2.4, the number of distinct triangles in the graph  is equal to

,

since and (see p.147 of [6]).

Remark 3.1.1: If is even then  and the term corresponding to  in the above product is zero so that  contains no triangles.

Example 3.1.2: Consider the Euler totient Cayley graph for. Here . So the number of distinct triangles in the graph  is

.

3.2. Enumeration of Triangles in the Quadratic Residue Cayley Graph

Let  be an odd prime and consider the set of the quadratic residues modulo. Let. Then  is a symmetric subset of the additive abelian group. The quadratic residue Cayley graph is the graph whose vertex set  and the edge set

.

For any vertex  in, we have and

and  and

are consecutive quadratic residues modulo. Thus

,

where  denotes the number of pairs of consecutive integers less than, since  is a subgroup of the multiplicative group, one can see as in the case of Euler totient Cayley graph that

for all .

So by the Theorem 2.4 the number of distinct triangles in the graph  is

=

If (mod), then, and (see section 10.1 of [1]). So the number of distinct triangles in  is.

If(mod), then,andso that the number of distinct triangles in is .

Example 3.2.1: Consider the quadratic residue Cayley graph.Here  (mod). So the number of distinct triangles in is equal to

.

Example 3.2.2: Consider the quadratic residue Cayley graph.

Here (mod). So the number of distinct triangles in  is equal to .

Acknowledgements

The authors express their thanks to Prof. L. Nagamuni Reddy for his suggestions during the preparation of this paper.

References

1. G. Andrews, Number Theory, Dover publications Inc.,1971.
2. P. Berrizbeitia and R. E. Giudici, Counting Pure k-cycles in Sequences of Cayley graphs, Discrete Maths. 149 (1996), 11-18.
3. P. Berrizbeitia, and R. E. Giudici, On cycles in the Sequence of Unitary Cayley graphs, Reporte Técnico No.01-95, Universidad Simon Bolivar, Dpto.de Matahematicas, Caracas, Venezula (1995).
4. T. Chalapati, L. Madhavi and S. Venkata Ramana, Enumeration of Triangles in a Divisor Cayley graph, MEJS 1 (2013), 163-173.
5. I. Dejter and R. E. Giudici, On Unitary Cayley graphs, JCMCC 18 (1995), 121 – 124.
6. E. Dickson, History of Theory of Numbers, Vol.1,Chelsea Publishing Company, 1952.
7. B. Maheswari and L. Madhavi, Enumeration of Triangles and Hamilton Cycles in Quadratic Residue Cayley graphs, Chamchuri Journal of Mathematics 1 (2009), 95-103.
8. B. Maheswari and L. Madhavi, Enumeration of Hamilton Cycles and Triangles in Euler totient Cayley graphs. Graphs Theory Notes of New York LIX (2010), 28-31.
9. L.Madhavi, Studies on Domination Parameters and ‘Enumeration of Cycles in some Arithmetic Graphs, Doctoral Thesis, Sri Venkateswara University, Tirupati, India (2002).
10. N.Vasumathi, Number Theoretic Graphs, Doctoral Thesis, S.V.University, Tirupati, India (1994).

 Contents 1. 2. 3. 3.1. 3.2.
Article Tools