Enumeration of Triangles and Hamilton Cycles in Quadratic Residue Cayley Graphs

Graph Theory has been realized as one of the most useful branches of Mathematics of recent origin, finding widest applications in almost all branches of sciences, social sciences, engineering and computer science.

The introduction of the concepts of Number Theory, particularly, the “Theory of congruences” in Graph Theory, paved the way for the emergence of a new class of graphs, namely, “Arithmetic Graphs”.

The quadratic residue Cayley graph $G(Z_p,Q),$ that is the Cayley graph associated with the set of quadratic residues modulo an odd prime $p$, which is defined as follows. Let $p$ be an odd prime, $S$ the set of quadratic residues modulo $p$ and let $S =\{s, n - s/s \in S\}.$ The quadratic residue Cayley graph $G(Z_p,Q)$ is defined as the graph whose vertex set is $Z_p = \{0, 1, 2, \ldots, p-1\}$ and the edge set is $E = \{(x, y)/x - y$ or $y - x$ is in $S\}.$

Let $n \ge 1$ be an integer and let $S = \{r/r < n$ and $(r, n) = 1\}.$ The Euler Totient Cayley Graph $G(Z_p, \phi),$ is defined as the graph whose vertex set is $Z_n = \{0, 1, 2, \ldots, n - 1\}$ and the edge set is $E = \{(x, y)/x - y$ or $y - x$ is in $S\}.$

In this paper we present the enumeration of triangles and disjoint Hamilton cycles for quadratic residue Cayley graph $G(Z_p,Q)$ and Euler Totient Cayley Graph $G(Z_p,\phi).$