1
$\begingroup$

A caterpillar or caterpillar tree is a tree in which all the vertices are within distance 1 of a central path.

From Wikipedia, I see that their count is also available in OEIS A005418. My question is, given $n$ vertices, is there a program to generate them? For example, I want to obtain all caterpillar graphs with 11 vertices.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

Here is a SageMath code generating caterpillar graphs on $n$ nodes based on enriching a path graph with leaves. As an example it shows all such graphs on 6 nodes.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ It's very much overkill to do canonical labelling to eliminate duplicates. if tuple(V) > tuple(reversed(V)): continue suffices. $\endgroup$
    – Peter Taylor
    Commented Jun 12 at 10:32
  • 1
    $\begingroup$ @PeterTaylor: Indeed, thanks for the suggestion! I've updated the code, although for the case of $n=11$ with just $528$ graphs, it does not matter much. $\endgroup$
    – Max Alekseyev
    Commented Jun 12 at 13:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .