# Spanning $k$-trees

##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

1. 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.

1. 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.

• I'll add a question: the threshold problem. What is the threshold for the appearance of a spanning k-tree in the binomial random graph?
– Bach
Nov 30 '20 at 7:18
• OK, it seems like there's an answer to the question I've added, at least for k=2: according to Riordan's theorem, if p>>n^{-1/2}, 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.
– Bach
Dec 6 '20 at 12:46

Regarding the question 1a, Bern showed that checking existence of a spanning $k$-tree in a graph is NP-complete for any fixed $k \geq 2$ (also see another, more accessible relevant paper by Cai and Maffray). This implies that questions 3 and 4 are at least as hard (indeed, each of these problems contains checking existence as a special case), and question 2a is unlikely to have a formula computable within reasonable time (unlike the polynomial-computable Laplacian cofactor for the number of trees).
The answers to questions regarding simplicial complexes may depend on the way we represent $k$-trees as complexes. Probably the most natural way to do that is to define a $k$-tree complex as a set of $k$-simplices obtained sequentially (from an initial set of a single $k$-simplex) by choosing a simplex $K$ and adding new simplex $K'$ to the set, so that $K'$ is different from $K$ in a single vertex not present in any previous simplex. However, we can notice that this problem is not easier than the problem of a spanning $k$-tree existence in a graph. Indeed, for any $k$ we can reduce from the graph problem to the simplicial problem simply by listing all $(k + 1)$-cliques (notice that since $k$ is fixed, the reduction is proper polynomial); the answer for that instance of the simplicial problem could be converted to a spanning $k$-tree of the original graph, and vice versa. This implies that the problem 1b is NP-complete whenever $k \geq 2$, and the problem 2b is not easier.
As for the general question about extending results from trees to $k$-trees, the intuition is probably that spanning $k$-trees of $K_n$ can be tamed (in light of results mentioned in OP), while spanning $k$-trees of a general graph may possess a much more complex structure not exhibited by spanning trees.