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