# caterpillar graphs in sage

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

How to define caterpillar graphs in sage? is it already implemented?

Kindly help me with this.

Thank you.

edit retag close merge delete

Sort by » oldest newest most voted

You can start from a path graph and then add the edges along this path. You can define the following function:

sage: def caterpillar(L):
....:     k = len(L)
....:     G = graphs.PathGraph(k)
....:     for i,n in enumerate(L):
....:         for _ in range(n):
....:             k += 1
....:     return G


Then calling for example caterpillar([3,1,0,7]) will result in a caterpillar graph with a path of length 4 and 3,1,0,7 vertices attached to them in that order.

more

You can use G = graphs.RandomLobster(20, .5, 0).

more

Can you please explain to me what is the number of vertices and vertices of degree on in $G$? It keeps changing when I run. Thank you.

( 2019-08-05 03:43:37 -0500 )edit

Most of the methods are well documented, so please check the documentation of the Random Lobsters generator.

The parameters of graphs.RandomLobster(n, p, q) are the number of nodes n of the generated graph, the probability p of attaching a pending edge to the main path and the probability q of attaching an edge to an edge of previous level. Setting q=0 ensure that you get a Random Caterpillar.

Of course it's random, so two successive calls give different results.

Otherwise, use the method proposed by tmonteil

( 2019-08-05 06:58:03 -0500 )edit