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



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



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



Spanning $k$-trees
Regarding the question 1a, Bern [showed](http://dl.acm.org/citation.cfm?id=913465) 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](http://www.sciencedirect.com/science/article/pii/0166218X9390228G) 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.


