Algunas propiedades sobre grafos unitarios de Cayley

DANIEL A. JAUME; DENIS E. VIDELA; ELIAS CANCELA

Tucuman

Congreso; UMA 2011; 2011

For a positive integer $n>1$ the unitary Cayley graph $X_{n} = Cay(Z_{n}, U_{n})$ is defined by the additive group of the ring $Z_{n}$ of integers mod $n$ and the multiplicative group $U_{n}$ of its units. If we represent the elements of $Z_{n}$ by the integers $0, 1,..., n-1$ then it is well known that $Un = {a \in Z_{n} : gcd(a, n) = 1}$. So $X_{n}$ has vertex set $V(X_{n}) = Z_{n} = {0, 1,..., n-1} $ and edge set $ E(X_{n}) = {\{a, b\} : a, b \in Z_{n}, gcd(a-b, n) = 1} $ Unitary Cayley graphs are highly symmetric. They have some remarkable properties connecting graph theory and number theory [2]. Despite numerous interconnection schemes proposed for distributed multicomputing, systematic studies of classes of interprocessor networks, that offer speed-cost tradeoffs over a wide range, have been few and far in between. A notable exception is the study of Cayley graphs that model a wide array of symmetric networks of theoretical and practical interest. Properties established for all, or for certain subclasses of, Cayley graphs are extremely useful in view of their wide applicability [1]. In this work we prove a generalization of a result of Klotz and Sander [2] about of the number of common neighbors of two vercites in a unitary Cayley graph. Theorem: Given k vertices $v_{1}, v_{2},..., v_{k}$ of a unitary Cayley graph $X_{n}$, the number of common neighbors of them is $N(v1, v2,..., vk) = (n/rad(n))Prod_{p|n} {(p-Delta_{p}(v_{1}, v_{2},..., vk))} $ where $Delta_{p}(v_{1}, v_{2},..., v_{k}) = |{v1, v2,..., vk}|$ We also count the number of squares and pentagons in Xn. And we conjecture that the unitary Cayley graphs are pancyclics (i.e. they have cycles of every length).