1
$\begingroup$

I am not sure if the title makes a whole lot of sense, but what I am trying to do is generate all non-isomorphic trees that obey the following:

1) Each vertex (including leaves) has one of two labels (A or B)

2) Those that are labeled B may have a maximum degree of 3 (at most three neighbors)

3) Those that are labeled A may have a maximum degree of 2 (at most two neighbors)

A few examples (Trees of Sizes (n)=4 and 5, with the number of A labeled vertexes = n-1 )

Size 4 :                          Size 5

B-A-A-A                         B-A-A-A-A
A-B-A-A                         A-B-A-A-A
                                A-A-B-A-A 

A-B-A                           A-B-A-A
  |                               |
  A                               A                            

I should note also that although my examples are of #A labeled vertexes=n-1, I am interesting in generating all of the tree with #A=n, n-1, n-2, n-3, n-4, ...n-k as well.

I feel like something like this has to have been enumerated before, but I am not sure what to call these type of trees, and as such I have been having a hard time finding other similar work. I do know that this is similar to the counting of "Boron Trees" ( OEIS A0514519 ) but its not quite right.

EDIT I forgot to mention that I have asked a similar question over at the general stack-overflow webpage, but haven't heard anything yet (link below). Currently, my attempts to generate the non-isomorphic structures is performed through a "stupid" monte-carlo technique: generate a random tree with a given number of A and B types, compare to all other trees generated, delete if isomorphic to any of them (this is ~N^2 computations, it can be made trivially parallel, but it requires lots of threads to be efficient for trees larger than 12. Also it isn't strictly guaranteed to give me all of the structures).

Stack-overflow question: Determining unique, site-labeled, lattice-trees (polynomino-like lattice-embedded graphs); not quite polyomino hashing

$\endgroup$
1
$\begingroup$

I have had similar problems listing 'labelled' objects (see note at the end).

For your case, I don't think that the A/B labels matter that much. They are shorthand for degree restrictions on the vertices. A broad outline of an approach that could work is, for trees on $n$ vertices:

  1. List all degree sequences of length $n$ -> $D_0 ... D_m$
  2. For some degree sequence $D_i$ make all trees with that sequence -> $T_0 ... T_l$ (eg with the method from this paper)
  3. Reject isomorphic trees

Now as you point out, comparing a new object to all previously generated ones is expensive - of course you only have to check each $T_i$ against all other $T$ for some $D_j$ (since two trees with different degree sequences cannot be isomorphic).

Alternatively, you could use the canonical path augmentation method of Brendan McKay and there may be other ways.

For part 2. you can't just use the Havel-Hakimi algorithm as that will only give you one example not all of them. I'm not 100% sure yet how to avoid generating identical (not just isomorphic) versions but in principle you just try all possible subsets of remaining vertices to connect to at each step.

As an example, consider the 2,3 trees on 7 vertices. These must have $n - 1$ edges, and therefore a degree sum of $2(n - 1)$ - that is, 12. So we partition 12 into 7 parts of at most 3. Like this:

enter image description here

where at the bottom, I think you have the polyomino objects that you mention on SO. As you may notice, for the degree sequence $2^5.1^2$ there is only one possible tree (the line graph) and that is the end of the possible partitions.


As an aside:

I have had similar problems in generating (listing) chemical graphs. The difficulty for me is that I don't exactly want 'labelled' objects - these usually refer to graphs where every vertex has a unique number. I also don't want 'colored' graphs, as these usually refer to 'proper' colorings where adjacent vertices have different colors.

$\endgroup$
  • $\begingroup$ Just a clarification, the example you provide, was that generated from the Havel-Hakimi algorithm or was it just random generation/rejection with each degree distribution? $\endgroup$ – Hobbes May 10 '16 at 12:52
  • $\begingroup$ @Hobbes It was done on paper - so a random selection. HH would only give you the second one - 3(3(2(1)1)1,1). There's an efficient way to generate all realisations of a degree sequence due to Zoltán Király in the paper "Recognizing Graphic Degree Sequences and Generating All Realizations" but you might find simpler but less efficient ways to be useful as a starting point. $\endgroup$ – gilleain May 10 '16 at 13:00
  • $\begingroup$ thank you for the paper reference. It should help $\endgroup$ – Hobbes May 11 '16 at 13:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.