1
$\begingroup$

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)
$\endgroup$
4
  • $\begingroup$ I see. The algorithm used for counting also takes care of these issues. Can't that be used to generate the trees? $\endgroup$ Aug 4, 2023 at 8:52
  • $\begingroup$ @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. $\endgroup$
    – licheng
    Aug 4, 2023 at 9:08
  • $\begingroup$ 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. $\endgroup$
    – Discrete lizard
    Aug 4, 2023 at 11:24
  • $\begingroup$ @Discretelizard I want to try enumeration first. As for the properties, I mainly focus on observing some non-Hamiltonian $4$-trees. $\endgroup$
    – licheng
    Aug 4, 2023 at 11:35

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.