Enumeration of Triangles in Cayley Graphs
Levaku Madhavi^{1}, Tekuri Chalapathi^{2}^{, *}
^{1}Department of Applied Mathematics, Yogi Vemana University, Kadapa, A. P., India
^{2}Department of Mathematics, Sree Vidyanikethan Engineering College, A. Rangampet, Tirupati, A. P., India
Email address:
To cite this article:
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