Uniquely Kr-Saturated Graphs: Experiment #1

by Derrick Stolee

My paper with Stephen Hartke, Uniquely K_r-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 K_r-saturated graphs, which led to many new examples. In a future post, we will discuss a second computational experiment within this paper.

The Problem

A graph G is uniquely H-saturated if G contains no copy of H as a subgraph and for every missing edge uv \notin E(G) there is exactly one subgraph of G + e isomorphic to H. This is a very restrictive condition, and there may not actually exist any (finite) uniquely H-saturated graphs for some graphs H. As a technical point, we only consider graphs G with |V(G)| \geq |V(H)|.

This concept was defined by Cooper, Lenz, LeSaulnier, Wenger, and West and they made some characterizations when H = C_k, the cycle on k vertices. For instance, the uniquely C_3-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 C_4-saturated graphs. Wenger later proved that the uniquely C_5-saturated graphs are exactly the friendship graphs, and uniquely C_k-saturated graphs do not exist for k \in \{6,7,8\}. He conjectures that uniquely C_k-saturated graphs do not exist for larger values of k.

We focus on the case H = K_r, the complete graph of order r for r \geq 4. Observe that when r = 3, we have K_3 \cong C_3 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.

r-Primitive Graphs

If G is uniquely K_r-saturated with a dominating vertex x, then x is in every maximal clique and so G-x is uniquely K_{r-1}-saturated. We say a uniquely K_r-saturated graph is r-primitive if it has no dominating vertex. Thus, all uniquely K_r-saturated graphs are given by taking an (r-\ell)-primitive graph and joining it to a copy of K_{\ell}.

For example, the a,b-book is formed by joining K_a to an independent set of size b. The (r-2),(n-r+2)-books are uniquely K_r-saturated, since the clique number is r-1 and every missing edge has both endpoints in the independent set and forms an r-clique with the r-2 vertices across the join. However, removing the r-2 vertices in the original clique results in an independent set, which is 2-primitive.

In the case r = 3, a uniquely K_3-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 r \geq 3, there is at least one r-primitive graph: \overline{C_{2r-1}}, the complement of the cycle on 2r-1 vertices. Collins, Cooper, and Kay found a few more 4-primitive graphs, shown below.

Figure 1. Some 4-primitive graphs of Collins, Cooper, and Kay.

From these examples and the results of Hoffman and Singleton, Cooper made the following conjecture:

Conjecture. For all r \geq 3, there are a finite number of r-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 r-primitive graphs are regular, but we will see that there is at least one irregular r-primitive graph.

Experiment #1: Orbital Branching with K_r-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 nauty).

For a given search, we will fix integers r and n with n > r. We will search for a uniquely K_r-saturated graph of order n. Our data structure is a trigraph of order n, 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 0, 1, and * correspond to white, black, and gray, respectively.)

For a pair of vertices u, v, a K_r-completion of uv is a set S of r-2 vertices such that S is a clique of black edges and all edges between \{u,v\} and S are black. A trigraph T with no gray edges corresponds to a uniquely K_r-saturated graph if and only if the following two constraints hold:

  • (C1) There is no black r-clique.
  • (C2) Every vertex pair has at most one black K_r-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 K_r-completion.

This constraint is satisfied by any solution, but not by every partial solution (simply take some black edges which appear in a K_r-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 K_r-completion. Again, we will take symmetry into account and only add one representative K_r-completion.

Let T be a trigraph with at least one gray edge. As before, we will select an orbit {\mathcal{O}} of gray edges.

  • Branch 1: Select a representative gray edge v_iv_j in {\mathcal{O}} and set it to white.
    • Sub-Branch: For every orbit* \mathcal{A} of (r-2)-sets of V(G) \setminus \{v_i,v_j\}, select a representative S \in \mathcal{A} and set black edges to make S a K_r-completion for v_iv_j.
  • Branch 2: Set all gray edges v_iv_j \in \mathcal{O} to be black.

*When we select orbits of (r-2)-sets, we set-wise stabilize \{v_i, v_j\} so the orbits are taken with respect to the edge we are modifying.

Figure 2. The two-stage branching process.

Now, we can follow this branching procedure to find all uniquely K_r-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 r-primitive graphs? Yes, if we determine all r-primitive graphs for all r \leq r_0, then we also exactly the uniquely K_{r}-saturated graphs in this range. However, the only constraint we gain is to guarantee a maximum degree of at most n(T)-1. If someone could prove stronger properties of r-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).

Results

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 3-primitive graphs, and the two 4-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).

Figure 3. The known r-primitive graphs. Green circles are independent sets. Blue circles are odd cycle complements. Red circles are previously-known graphs. Black diamonds are graphs found by this search.

One thing I should point out is that one of the 5-primitive graphs of order 16 is irregular! The other 5-primitive graph of order 16 is regular, which hints to the difficulties in proving degree bounds on r-primitive graphs.

In the next post, we’ll talk about a second computational experiment which led to some new infinite families of r-primitive graphs. (The values of r changes, so this does not violate the conjecture.)

Related Posts

Introduction to Orbital Branching

Computing Orbits with nauty

Ranking and Unranking of Combinations and Permutations

References

J. Cooper, J. Lenz, T. D. LeSaulnier, P. S. Wenger, D. B. West, Uniquely C_4-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 K_r-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 C_k-saturated graphs, in preparation.

Advertisements