##k-trees

A $k$-tree is a graph defined as follows: (They were defined by Harary and Palmer.)

a) A complete graph with $k$ vertices is a $k$-tree.

b) A $k$-tree on $n$ vertices $T$ is obtained by a $k$-tree on $n-1$ vertices $S$ by adding a new vertex and connecting it to all the $k$ vertices of a complete subgraph of $S$ with $k$ vertices.

We can also regard a $k$-tree instead of a graph, as a $k$-dimensional simplicial complex, or as a $k+1$-uniform hypergraph. (We can also regard it as a $r$-uniform hypergraph for $2 \le r \le k+1$.)

#The questions

## The decision problem

1a) Is there an efficient algorithm to tell if a graph contains a spanning $k$-tree.

1b) Is there an efficient algorithm to tell if a $k$-dimensional simplicial complex contains a $k$-tree. (Regarded, this time, as a $k$-dimensional simplicial complex.)

Of course, for $k=1$ a graph contains a tree iff it is connected.

## The counting problem

2a) Given a graph $G$ is there a matrix-tree type theorem for the number of spanning $k$-trees of $G$?

2b) More generally, given a $k$-dimensional simplicial complex $K$ is there a matrix-type formula for the number of spanning $k$-trees. (Regarded as $k$-dimensional simplicial complexes.)

## The sampling problem

- Is there a simple way to sample a uniformly-random spanning $k$-tree of a given graph $G$?

For $k=1$ there are various miraculous important ways to sample uniform spanning trees.

## Minimal spanning $k$-trees

For $k=1$ the famous greedy algorithm efficiently find the minimum-weight spanning tree.

- Given weights on edges is there an algorithm for finding minimum spanning $k$-tree?

## Bach's threshold problem.

(Added in a comment, Nov. 2020)

What is the threshold for the appearance of a spanning k-tree in the binomial random graph?

## The general theme

In general, to what extent results about trees extend or fail to extend to $k$-trees.

##Some more background

Cayley's formula for the number of trees with $n$ labelled vertices was extended to $k$-trees by Beineke and Pippert. A Prufer type correspondence by C. Renyi and A. Renyi allows efficient sampling (uniformly) all $k$-trees with $n$ labelled vertices.

threshold problem. What is the threshold for the appearance of a spanning k-tree in the binomial random graph? $\endgroup$every(given) 2-tree appears with high probability, and if p=n^{-1/2} then by the union bound none of these will appear whp. Didn't check for k>2. $\endgroup$