It is known (and can easily be seen) that a unitary Cayley graph on $n=\prod_ip_i$, ($p_i$ distinct primes) vertices with $n$ square-free can be recognized as the tensor product of the graphs $K_{p_i}$, where $K_n$ denotes the complete graph on $n$ vertices. Is a similar characterization possible for all other unitary Cayley graphs i.e., when $n$ is not square-free? Further is such a characterization possible for all perfect Cayley graphs?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
It could be seen that any unitary graph can be written as the tensor product of several balanced complete multipartite graphs. If we denote the balanced complete multipartite graphs having $k$ parts with $r$ vertices in each part as $K(r,k)$, then any unitary cayley graph on $n$ vertices, where $n$ factors as $n=\prod_{i}p_i^{r_i}$ can be recognized as a tensor product of the graphs $K(p_i^{r_i-1},p_i)$.
I feel the same extends to any perfect Cayley graph, but the value of $r_i$ is not so easily determined. The value of $min(p_i)$ is nothing but the clique number of the graph.