Computational Combinatorics Roundup: October

It is the end of October, so let’s start a monthly tradition of listing new papers in computational combinatorics. This list is likely not complete, so please comment or send me an email if there is a recent paper that I missed. Some of these papers are not exactly “new” but are papers I’ve discovered since the last reference list. Since I plan to do this regularly, send me an email when you see a new paper using computational methods and I will add it to the next reference list update.

Uniquely Kr-Saturated Graphs: Experiment #2

In the previous post, we defined uniquely -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 -primitive graph is a uniquely -saturated graph with no dominating vertex. Since Cayley graphs are regular, we search for -primitive Cayley graphs.

Uniquely Kr-Saturated Graphs: Experiment #1

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.

Introduction to Orbital Branching

Orbital branching is an example of a method that started in combinatorial optimization but has been applied for computations in pure combinatorics. In this post, we’ll introduce this method while in the context of generating combinatorial objects. The major difference between this perspective and the original goal is that we are generating all feasible solutions (which are probably rare) while the original applications were finding optimal solutions (and feasible solutions were plentiful).

Computing Orbits with nauty

Now that we can compute canonical labelings with nauty, we will now find out how to modify that code in order to compute orbits of any rankable object within a graph. We will focus on the orbits of certain vertex sets, although the technique generalizes to -tuples of vertices, as well. Really, all you need is an object with a ranking and unranking function to make this technique work.