How one can get a tree with exactly a given degree sequence and a given set of edges?

asked 2017-08-27 12:45:38 +0200

anonymous user


I tried for the following graph but in the resultant graph edge set changes.

G = graphs.DegreeSequenceTree([1,2,3,1,3,1,3,1,1]) G.edges(labels=False) [(6,1),(1,5),(5,0),(5,3),(3,2),(3,8),(8,4),(8,7)]

edit retag flag offensive close merge delete


Not entirely clear what you mean by "the resultant graph edge set changes". Could you please explain what you mean?

Also, if the set of edges is given, isn't this enough information to construct the tree?

fidbc gravatar imagefidbc ( 2017-08-27 16:53:28 +0200 )edit

Yes you are correct. We can construct but when I run this programme in sage the edge set changes. The edge set that appears in the output graph does not match with the edge set that has been given in the question. I need a tree exactly with these given edge set. If possible please have a look.


rewi gravatar imagerewi ( 2017-08-27 19:49:37 +0200 )edit

Sorry, still not understanding. The DegreeSequenceTree will provide a tree that has the given degree sequence, and the output is correct. Can you enforce the routine to provide a given set of edges? Then I see no point on calling the DegreeSequenceTree method.

Maybe you are asking whether the graph given by a certain set of edges has some degree sequence? Please explain.

fidbc gravatar imagefidbc ( 2017-08-27 21:11:02 +0200 )edit

The degree sequence of the required tree is [1,2,3,1,3,1,3,1,1]. This is a tree with vertex set {0,1,2,3,4,5,6,7,8}. Now ,I want to construct a tree having this degree sequence and edge set of my required tree is as given below: {(6,1),(1,5),(5,0),(5,3),(3,2),(3,8),(8,4),(8,7)} where (i,j) denotes the edge between the vertex i,j in the tree where i,j belongs to {0,1,2,3,4,5,6,7,8}. But when I run this code in sage I am getting edge set as:{(0,1),(1,2),(2,6),(2,3),(3,7),(3,4),(4,8),(4,5)}.There is no problem with degree sequence it is ok. Only problem is that I am not getting the required edge ...(more)

rewi gravatar imagerewi ( 2017-08-27 22:43:39 +0200 )edit
  1. When you say required edge set, where in the code is that part of your input?

  2. Out of curiosity, if you provide the edge set beforehand, why use DegreeSequenceTree?

Perhaps a bit more context on what you are trying to achieve would help.

Note that given a degree sequence, there may be too many ways to realize the degree sequence. In fact, it is not necessarily the case that you obtain isomorphic graphs. Perhaps what you are looking for is an invariant way of labelling the tree? In which case you can use canonical_labelling. This way you can canonically label the graph you have from the required edges and also the graph output from the DegreeSequenceTree and just compare edge sets to test equality.

fidbc gravatar imagefidbc ( 2017-08-27 23:53:23 +0200 )edit