Uniquely Kr-Saturated Graphs: Experiment #1
by Derrick Stolee
My paper with Stephen Hartke, Uniquely -Saturated Graphs appeared recently on the Electronic Journal of Combinatorics. This publication prompted our recent shift to the technique of orbital branching. In this post, we will see how we extended orbital branching to generate uniquely -saturated graphs, which led to many new examples. In a future post, we will discuss a second computational experiment within this paper.
A graph is uniquely -saturated if contains no copy of as a subgraph and for every missing edge there is exactly one subgraph of isomorphic to . This is a very restrictive condition, and there may not actually exist any (finite) uniquely -saturated graphs for some graphs . As a technical point, we only consider graphs with .
This concept was defined by Cooper, Lenz, LeSaulnier, Wenger, and West and they made some characterizations when , the cycle on vertices. For instance, the uniquely -saturated graphs are exactly stars and Moore graphs of diameter 2. These Moore graphs were determined by Hoffman and Singleton to be finite. Cooper et al. also proved that there are a finite number of uniquely -saturated graphs. Wenger later proved that the uniquely -saturated graphs are exactly the friendship graphs, and uniquely -saturated graphs do not exist for . He conjectures that uniquely -saturated graphs do not exist for larger values of .
We focus on the case , the complete graph of order for . Observe that when , we have and the graphs are all but completely characterized. For extremal graph theory problems, such as finding the Turán or saturation numbers, the first case is usually the complete graph. In this case, the complete graph was not solved first because it presents some interesting complications.
If is uniquely -saturated with a dominating vertex , then is in every maximal clique and so is uniquely -saturated. We say a uniquely -saturated graph is -primitive if it has no dominating vertex. Thus, all uniquely -saturated graphs are given by taking an -primitive graph and joining it to a copy of .
For example, the -book is formed by joining to an independent set of size . The -books are uniquely -saturated, since the clique number is and every missing edge has both endpoints in the independent set and forms an -clique with the vertices across the join. However, removing the vertices in the original clique results in an independent set, which is 2-primitive.
In the case , a uniquely -saturated graph is a star or a Moore graph. Since a star has a dominating vertex, the 3-primitive graphs are exactly the Moore graphs of diameter 2. Hoffman and Singleton proved there are a finite number of these graphs, so there are a finite number of 3-primitive graphs.
For every , there is at least one -primitive graph: , the complement of the cycle on vertices. Collins, Cooper, and Kay found a few more 4-primitive graphs, shown below.
From these examples and the results of Hoffman and Singleton, Cooper made the following conjecture:
Conjecture. For all , there are a finite number of -primitive graphs.
The previous results that characterize uniquely saturated graphs used an eigenvalue technique, the first step of which was to prove that the graphs are regular. It was previously attempted to prove that -primitive graphs are regular, but we will see that there is at least one irregular -primitive graph.
Experiment #1: Orbital Branching with -Completions
In the previous post, we discussed orbital branching and how it is essentially a branch-and-bound search with automorphisms taken into account when possible. A fundamental discussion is that of the symmetries involved. For today, we will consider our object to be a trigraph (discussed in Computing Orbits with
For a given search, we will fix integers and with . We will search for a uniquely -saturated graph of order . Our data structure is a trigraph of order , where white edges are definitely non-edges, black edges are definitely edges, and gray edges are undecided edges. (In terms of the previous discussion, the variables correspond to pairs and the values , , and correspond to white, black, and gray, respectively.)
For a pair of vertices , a -completion of is a set of vertices such that is a clique of black edges and all edges between and are black. A trigraph with no gray edges corresponds to a uniquely -saturated graph if and only if the following two constraints hold:
- (C1) There is no black -clique.
- (C2) Every vertex pair has at most one black -completion.
These two constraints can be evaluated on a trigraph with gray edges as well, so as we build a trigraph from the all-gray trigraph we will verify these constraints at every step.
However, performing standard orbital branching with these constraints will lead to a very slow generation algorithm. The biggest reason is that it will take several steps before either of these constraints are even close to being violated! Instead, we will modify our augmentation to take the following additional constraint into account:
- (C3) Every white edge has exactly one -completion.
This constraint is satisfied by any solution, but not by every partial solution (simply take some black edges which appear in a -completion and change them to gray). But, this will guide our two-stage orbital branching procedure.
The first stage of the branching will be just as in standard orbital branching: select an orbit of gray edges and either change one representative to white or change all representatives to black. The second stage occurs when we change a gray edge to white. We will verify constraint (C3) by adding black edges until the white edge has a -completion. Again, we will take symmetry into account and only add one representative -completion.
Let be a trigraph with at least one gray edge. As before, we will select an orbit of gray edges.
- Branch 1: Select a representative gray edge in and set it to white.
- Sub-Branch: For every orbit* of -sets of , select a representative and set black edges to make a -completion for .
- Branch 2: Set all gray edges to be black.
*When we select orbits of -sets, we set-wise stabilize so the orbits are taken with respect to the edge we are modifying.
Now, we can follow this branching procedure to find all uniquely -saturated graphs. At every step, we verify constraints (C1) and (C2) and if one is violated we prune the search node.
You may be asking: Why didn’t the search restrict to find only -primitive graphs? Yes, if we determine all -primitive graphs for all , then we also exactly the uniquely -saturated graphs in this range. However, the only constraint we gain is to guarantee a maximum degree of at most . If someone could prove stronger properties of -primitive graphs, we could integrate them into the search to find gains in computation time! Alas, no such statements have appeared (and I personally failed to prove anything of the kind).
By implementing this search with my TreeSearch project, the search could be run in a massively parallel environment. I am very lucky to have access to the Open Science Grid through the University of Nebraska Campus Grid. At times, I was able to have 5000 simultaneous processes, so while I report computation times here, I did not actually wait 40+ years for these computations to complete. In fact, the real-time computation was only a couple weeks, with plenty of lag time where I was unable to immediately restart jobs. See the paper for a table of timing data.
What’s most important is to talk about the graphs we found! There where the cycle complements, the -primitive graphs, and the two -primitive graphs previously known. Other than these, we found 10 new graphs! Figure 3 shows the distribution of these graphs (see the paper for full constructions).
One thing I should point out is that one of the -primitive graphs of order 16 is irregular! The other -primitive graph of order 16 is regular, which hints to the difficulties in proving degree bounds on -primitive graphs.
In the next post, we’ll talk about a second computational experiment which led to some new infinite families of -primitive graphs. (The values of changes, so this does not violate the conjecture.)
J. Cooper, J. Lenz, T. D. LeSaulnier, P. S. Wenger, D. B. West, Uniquely -saturated graphs, Graphs and Combinatorics, 28(2), 189-197 (2012).
D. Collins, J. Cooper, B. Kay, P. S. Wenger, personal communication, (2011).
S. G. Hartke, D. Stolee, Uniquely -Saturated Graphs, The Electronic Journal of Combinatorics, 19(4), P6, 41pp. 2012.
A. J. Hoffman, R. R. Singleton, On Moore graphs with diameters 2 and 3. IBM Journal of Research and Development 4(5), 497-504 (1960).
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).
J. Ostrowski, J. Linderoth, F. Rossi, and S. Smriglio. Orbital branching. In IPCO ’07: Proceedings of the 12th international conference on Integer Programming and Combinatorial Optimization, volume 4513 of LNCS, pages 104-118, Berlin, Heidelberg, 2007. Springer-Verlag.
D. Stolee, TreeSearch User Guide, (2011).
P. S. Wenger, Uniquely -saturated graphs, in preparation.