[Nauty-list] Generating graphs with fixed induced subgraph

Brendan McKay bdm at cs.anu.edu.au
Fri Feb 8 23:16:32 EST 2008

Gunnar reasonably wonders whether we really agree on the definition,
but let me answer the question as I understand it. We want to make
all the graphs on k+t vertices with a specified induced subgraph in
the first k vertices. Isomorphisms between two such graphs must map
the first k vertices of one to the first k vertices of the other
(this is the point that Gunnar highlighted).

There is no software in the nauty suite that covers this, but it
is reasonably routine. Suppose we have all the graphs with k+t-1
vertices. Let G be such a graph. Let A be its automorphism group
fixing the first k vertices. Take a new vertex v and join it to
some subset S of the vertices of G to make H. (We need to consider
exactly one such S out of each equivalence class of possibilities
under the action of S on the power set of V(G).) Now compute the
group B and canonical labelling of H, in each case with the first
k vertices fixed. Accept H if v is in the same orbit of B as the
vertex which is last in the canonical labelling; otherwise reject H.
The set of all such accepted graphs is the complete collection with
k+t vertices.

There are many variations and optimizations.


* Marko Milosevic <ninja643 at gmail.com> [080207 10:14]:
> On 2/7/08, Brendan McKay <bdm at cs.anu.edu.au> wrote:
> >
> >
> > I wonder if your subgraph is permanently distinguished (as if it has
> > a colour different from all the new vertices), or if you just want
> > the graphs that happen to have an induced subgraph isomorphic to
> > your required subgraph.  The former case is quite a bit easier than
> > the latter, since the latter requires searching for subgraphs in
> > addition to the one you started with.
> My graph is permanently distinguished, i.e. fixed on first k vertices. I
> want to add the remaining n-k vertices in all possible ways. I hoped that
> it's not too hard.
> Marko.

> _______________________________________________
> Nauty-list mailing list
> Nauty-list at cs.anu.edu.au
> http://dcsmail.anu.edu.au/cgi-bin/mailman/listinfo/nauty-list

More information about the Nauty mailing list