3
$\begingroup$

I need to generate/enumerate isomorphism classes of vertex-rooted graphs with the following properties. Let $\Delta$ be the maximal degree (say 3 for subcubic graphs) and $r$ the maximal distance of a vertex from the root (something like radius, even though the formal definition of radius of a graph is different). Note that the requirement also means the graphs are connected.

Note that rooted graphs are isomorphic if there exists an isomorphism that respects the root, i.e., sends root to root.

It is clear that for fixed $\Delta$ and $r$ there exist only finitely many such graphs. The number of them will be huge, but still drastically smaller than the number of all graphs or all bounded-degree graphs on the same number of vertices.

Example: For $\Delta=2$ and $r=1$ we would get exactly $4$ graphs: (1) just the root, (2) an edge with one vertex the root, (3) a cherry with the root in the middle and (4) a triangle with one vertex the root.

The case I am mostly interested in is $\Delta=3$ but if possible I would like to be more general.

Question: Is there some software or a collection that provides this? If possible, I would like to avoid coding the whole thing myself as this seems to be a rather complex task (generating non-isomorphic graphs in a reasonable efficient way).

I am aware of nauty, which can check isomorphism and also generates certain types of graphs. But after reading the manual, I think there is no option to generate rooted graphs (there is option to generate bounded-degree graphs, though).

Does anyone have an idea how to do this without spending a lot of time writing my own generator?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Nauty is the go-to software for isomorphisms. See this question $\endgroup$
    – adrianN
    Commented Jan 11, 2017 at 11:04
  • 1
    $\begingroup$ @adranN I am aware of nauty. It can generate bounded-degree graphs and this could be useful. The problem is as follows. Let us say $\Delta=3$ and $r=3$. With these parameters it should still be tractable to generate all graphs. But graphs of this type can have up to 22 vertices. And I cannot generate all graphs of maximal degree 3 on 22 vertices and then somehow choose a root and check the radius, because there is insanely many graphs of max degree 3 on 22 vertices. But there is substantially less graphs of max degree 3 and a root such that all vertices have distance at most 3 from the root. $\endgroup$
    – JS_
    Commented Jan 11, 2017 at 18:19

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.