Uniquely Kr-Saturated Graphs: Experiment #2

by Derrick Stolee

In the previous post, we defined uniquely K_r-saturated graphs and described a search to find all such graphs of a given order. One of these graphs was a 7-primitive graph of order 17. The graph is vertex-transitive, and all vertex-transitive graphs of prime order are Cayley graphs. Recall that an r-primitive graph is a uniquely K_r-saturated graph with no dominating vertex. Since Cayley graphs are regular, we search for r-primitive Cayley graphs.

Cayley Graphs and Cayley Complements

A Cayley graph is a graph that is defined by a group \Gamma and a set of generators S\subseteq \Gamma. We will only consider the undirected, unlabeled version of a Cayley graph. Let C(\Gamma,S) be the graph with vertex set \Gamma and has an edge ab if and only if ab^{-1} \in S or a^{-1}b \in S (i.e. there is an element s \in S such that a = bs or as = b). Every Cayley graph will be regular and vertex-transitive.

Actually, the 7-primitive graph of order 17 was not the first r-primitive Cayley graph that was known. We already had the complement of the cycle on 2r-1 vertices is r-primitive. One way to describe such a graph is to use the Cayley graph C({\mathbb Z}_{2r-1}, \{ 2, 3, \dots, r-1\}). However, using such a large generator set is unwieldy. Instead, let us consider the complement graph, which is just a cycle. Then, our graphs are the complements of the Cayley graph C({\mathbb Z}_{2r-1}, \{1\}).

Since the 7-primitive graph of order 17 has degree 12, it is easier to describe the complement which is 4-regular. The complement of C({\mathbb Z}_{17}, \{1,4\}) is 7-primitive. Since we now know of a new r-primitive graph which is the complement of a Cayley graph with a small generator set, we will consider searching for r-primitive Cayley complements. Let \overline{C}({\mathbb Z}_n, S) be the complement of the Cayley graph over {\mathbb Z}_n generated by S.

The Search

To search for r-primitive Cayley complements with small generator sets, we make one important change from the previous search method. In Experiment #1, we fixed a value of r and n and then searched for an r-primitive graph of order n. In Experiment #2, we will instead relax the values of r and n, and instead generate Cayley complements and determine what values of r and n fit the graph.

Our search method is to generate all possible sets S and then test \overline{C}({\mathbb Z}_n, S) for unique saturation over values of n > 2\max S. The reason for this lower bound is that we want the generators of S to be distinct and all less than n/2. Otherwise, we could have used a smaller generator set (or one with smaller maximum value). First, we make an assumption:

We will always place 1 in S. If our Cayley complement contains any primitive generator, then there is an isomorphic Cayley complement where the generating set contains 1. Graphs not containing a primitive generator may not even be connected! This simple assumption greatly decreases the search space, but there is no guarantee that an r-primitive Cayley complement has a primitive generator. It is possible that we have missed some examples.

A few parameters will define our search space:

  1. g : The size of S.
  2. m : The maximum value that can be placed in S.
  3. N : The maximum value for n.

If $latex S = \{ s_1 < \dots 1$ and then a choice for s_3 > s_2 and so on. This process defines a branching tree of depth g - 1. From each of the generator sets, we can begin testing each value of n in order. This test must check the following:

  1. What is the clique number of \overline{C}({\mathbb Z}_n, S)? Let it be r-1.
  2. For each generator s_i \in S, how many r-cliques are in \overline{C}({\mathbb Z}_n,S) + \{0,s_i\}? If ever not equal to 1, report failure.

If the above checks are satisfied, then the graph is r-primitive. To perform the above checks, we used Niskanen and Östergård’s cliquer library, which is the fastest open-source clique-finding and clique-counting algorithm (to my knowledge). It even has a way to short-circuit the counting method when more than one r-clique is found, which sped up the search significantly.


Table 1 shows the graphs we found for two generators.

S r n
\{ 1, 4\} 7 17
\{ 1, 6\} 16 37
\{ 1, 8\} 29 65
\{ 1, 10\} 46 101
\{ 1, 12\} 67 145

Table 1. r-primtive Cayley complements with g = 2.

Observe that the generator sets are of the form \{1, 2t\} for t \geq 2. If we consider t = 1, we have the generator set \{1,2\}. We do know of an r-primitive graph isomorphic to \overline{C}({\mathbb Z}_n, \{1,2\}) for n = 5, where the graph is empty and hence 2-primitive.

This collection of graphs has a nice pattern in their generator set, but the pattern in r and n is less obvious. We took these numbers and interpolated a polynomial in terms of t. Somewhat surprisingly, the resulting polynomials had degree 2 and integer coefficients. Thus, we have an immediate conjecture which we then proved.

Theorem. (Hartke, Stolee) Let t \geq 2 and set n = 4t^2+1 and r = 2t^2-t+1. Then, \overline{C}({\mathbb Z}_n, \{1, 2t\}) is r-primitive.

We found a similar pattern among the sets of three generators, given in Table 2.

S r n
\{ 1, 3, 4\} 4 13
\{ 1, 5, 6\} 9 31
\{ 1, 8, 9\} 22 73
\{ 1, 11, 12\} 41 133

Table 2. r-primtive Cayley complements with g = 3.

This collection does not completely match any pattern. However, this is due to the first row, where the graph \overline{C}({\mathbb Z}_{13}, \{1, 3, 4\}) is isomorphic to the Paley graph of order 13, which was previously found to be 4-primitive. Paley graphs are very special cases of Cayley graphs, so we remove that entry from his table. What we find is generator sets of the form \{1, 3t-1, 3t\} for t \geq 2. Again, if t= 1, the Cayley complement with generator set \{1,2,3\} over {\mathbb Z}_7 presents the empty graph which is 2-primitive. With these four values, we can again interpolate to find polynomials for r and n and then prove that the infinite family is r-primitive.

Theorem. (Hartke, Stolee) Let t \geq 2 and set n = 9t^2-3t+1 and r = 3t^2-2t+1. Then, \overline{C}({\mathbb Z}_n, \{1, 3t-1, 3t\}) is r-primitive.

There are eight other examples of r-primitive Cayley complements which we were not able to extend to infinite familites. Perhaps a smarter search will find more examples and this interpolating technique can present a pattern.

One thing is clear: this is an example where computational techniques help discover a conjecture that is then proven using standard methods. In the two-generator case, we used a counting method. In the three-generator case, we used a discharging method. The discharging is rather clean to prove the clique number, but it gets very technical when counting the number of r-cliques when adding an edge.

I leave you with some open questions in this area:

Question. Is there an r-primitive Cayley complement of even order?

Question. If \overline{C}({\mathbb Z}_n, S) is r-primitive, what group- or ring-theoretic properties does S have within {\mathbb Z}_n?

Question. Are there other groups \Gamma \not\cong {\mathbb Z}_n where some Cayley graph over \Gamma is r-primitive?


S. G. Hartke, D. Stolee, Uniquely K_r-Saturated Graphs, The Electronic Journal of Combinatorics, 19(4), P6, 41pp. 2012.

S. Niskanen, P. R. J. Östergård, Cliquer User’s Guide, Version 1.0, Communications Laboratory, Helsinki University of Technology, Espoo, Finland, Tech. Rep. T48, (2003).

D. Stolee, TreeSearch User Guide, (2011).