Ask Your Question

caterpillar graphs in sage

asked 2019-08-05 08:57:15 +0200

GA316 gravatar image

updated 2019-08-28 10:24:25 +0200

FrédéricC gravatar image

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 flag offensive close merge delete

2 Answers

Sort by » oldest newest most voted

answered 2019-08-05 12:49:51 +0200

tmonteil gravatar image

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):
....:             G.add_edge(i,k)
....:             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.

edit flag offensive delete link more

answered 2019-08-05 09:54:00 +0200

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

edit flag offensive delete link 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.

GA316 gravatar imageGA316 ( 2019-08-05 10:43:37 +0200 )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

David Coudert gravatar imageDavid Coudert ( 2019-08-05 13:58:03 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2019-08-05 08:57:15 +0200

Seen: 100 times

Last updated: Aug 05 '19