# Generating algorithm (or program) for $k$-trees

A $$k$$-tree is recursively defined as follows: $$K_k$$ is a $$k$$-tree and any $$k$$-tree on $$n+1$$ vertices is obtained by joining a vertex to a $$k$$-clique in a $$k$$-tree on $$n$$ vertices.

I have only seen some counting results for $$n$$-th order $$k$$-trees, like in the article below.

• A. Gainer-Dewar, Γ-species and the enumeration of $$k$$-trees. Electronic Journal of Combinatorics, 19(4) (2012).
• A.Gainer-Dewar, and Ira M. Gessel. "Counting unlabeled $$k$$-trees." Journal of Combinatorial Theory, Series A 126 (2014): 177-193.

3-trees:

3       1
4       1
5       1
6       2
7       5
8       15
9       58
10      275
11      1505
12      9003
13      56931
14      372973
15      2506312


4-trees:

4       1
5       1
6       1
7       2
8       5
9       15
10      64
11      331
12      2150
13      15817
14      127194
15      1077639


But for generating $$k$$-trees (not just counting), I haven't found the corresponding articles yet. (At present, I am particularly interested in the generation of 3-trees and 4-trees.)

I believe the difficulty I am facing is that when we are ready to add new vertices, there are many choices for the k-clique of of the old graph. Then we may need to filter out isomorphic cases.

PS: I have previously asked about the algorithm for identifying whether a graph is a k-tree. The user Highheath told me there is a linear algorithm, see Recognizing whether a graph is a k-tree.

Sage code to compute numbers of $$k$$-trees :

    # Set up a ring of formal power series
psr = PowerSeriesRing(QQ, 'x')
x = psr.gen()

# Compute the generating function for unlabeled Y-rooted k-trees fixed by permutations of a given cycle type mu.
# Note that mu should partition k
@cached_function
def unlY(mu, n):
if n <= 0:
return psr(1)
else:
ystretcher = lambda c, part: unlY(Partition(partition_power(part, c)), floor((n-1)/c)).subs({x:x**c})
descendant_pseries = lambda part: prod(ystretcher(c, part) for c in part)
return sum(x**i/i * descendant_pseries(partition_power(mu, i)).subs({x:x**i}) for i in xrange(1, n+1)).exp(n+1)

# Compute the generating function for unlabeled XY-rooted k-trees fixed by permutations of a given cycle type mu.
# Note that mu should partition k+1
@cached_function
def unlXY(mu, n):
if n <= 0:
return psr(0)
else:
ystretcher = lambda c: unlY(Partition(partition_power(mu, c)[:-1]), floor((n-1)/c)).subs({x:x**c})
return (x * prod(ystretcher(c) for c in mu)).add_bigoh(n+1)

# Compute the generating functions for unlabeled X-, Y-, and XY-rooted k-trees using quotients
ax = lambda k, n: sum(1/mu.aut() * unlXY(mu, n) for mu in Partitions(k+1))
ay = lambda k, n: sum(1/mu.aut() * unlY(mu, n) for mu in Partitions(k))
axy = lambda k, n: sum(1/mu.aut() * unlXY(Partition(mu + [1]), n) for mu in Partitions(k))

# Compute the generating function for unlabeled un-rooted k-trees using the dissymmetry theorem
a = lambda k, n: ax(k, n) + ay(k, n) - axy(k, n)

# Print the result
# ALERT: User must substitue values for k and n (number of hedra)
print a(kval, nval)

• I see. The algorithm used for counting also takes care of these issues. Can't that be used to generate the trees? Aug 4, 2023 at 8:52
• @InuyashaYagami A. Gainer-Dewar has also written a code based on Sage 5.0. I am adapting their code to the latest Sage 10 (see the post). (Currently, I don't have the ability to understand details in his paper.) As I am engaged in theoretical research (not algorithmic), I want to first generate non-isomorphic $k$-trees of a specific order, in order to find k-trees that satisfy certain properties. The implementation of a algorithm for generating $k$-trees, seeing those graphs, is my goal. Aug 4, 2023 at 9:08
• Do you specifically want to enumerate all $k$-trees of a given order, or do you just want to find some k-trees that satisfy certain properties? In the latter case, it may be better to encode these properties into e.g. a CSP and run a solver. This depends on the properties, of course. Aug 4, 2023 at 11:24
• @Discretelizard I want to try enumeration first. As for the properties, I mainly focus on observing some non-Hamiltonian $4$-trees. Aug 4, 2023 at 11:35