# What is the correct definition of $k$-tree?

As the title says, what is the correct definition of $$k$$-tree? There are several papers that talk about $$k$$-trees and partial $$k$$-trees as alternative definitions for graphs with bounded treewidth, and I've seen many seemingly incorrect definitions. For example, at least one place defines $$k$$-trees as follows:

A graph is called a $$k$$-tree if and only if either $$G$$ is the complete graph with $$k$$ vertices, or $$G$$ has a vertex $$v$$ with degree $$k − 1$$ such that $$G \setminus v$$ is a $$k$$-tree. A partial $$k$$-tree is any subgraph of a $$k$$-tree.

According to this definition, one can create the following graph:

1. Start with an edge $$(v_1, v_2)$$, a $$2$$-tree.
2. For $$i=1\ldots n$$, create a vertex $$v_i$$ and make it adjacent to $$v_{i-1}$$ and $$v_{i-2}$$.

Doing this would create a strip of $$n$$ squares with diagonals. Similarly, we can start creating a band from the first square in a direction orthogonal to the strip above. Then, we would have the first row and first column of an $$n \times n$$ grid. Filling in the grid is easy by creating vertices and joining them to the vertices to its above and to its left.

The end result is a graph that contains an $$n\times n$$ grid, which, in effect, is known to be of treewidth $$n$$.

A correct definition of $$k$$-trees has to be the following:

A graph is called a $$k$$-tree if and only if either $$G$$ is a complete graph with $$k$$ vertices, or $$G$$ has a vertex $$v$$ with degree $$k-1$$ such that the neighbor of $$v$$ forms a $$k$$-clique, and $$G \setminus v$$ is a $$k$$-tree.

Then, the grid-like graph described as above cannot be created.

Am I correct?

• Could you latex-ify your question - makes it easier to read. See meta.cstheory.stackexchange.com/questions/225/… for more details Sep 21, 2010 at 8:06
• With this definition ,I can not draw a 2_tree,will you please draw and send it for me?
– user32801
Apr 19, 2015 at 13:06

I basically agree with you, with just a tiny modification:

A graph $$G$$ is a $$k$$-tree if and only if either $$G$$ is a complete graph with $$k+1$$ vertices, or $$G$$ has a vertex $$v$$ such that the (open) neighborhood of $$v$$ forms a $$k$$-clique, and $$G - v$$ is a $$k$$-tree.

In other words, $$v$$ should have degree $$k$$, instead $$k-1$$ in your definition.

I personally prefer the bottom-up definition, but this is just a matter of taste:

• The complete graph on $$k+1$$ vertices is a $$k$$-tree.
• A $$k$$-tree $$G$$ with $$n+1$$ vertices ($$n\ge k+1$$) can be constructed from a $$k$$-tree $$H$$ with $$n$$ vertices by adding a vertex adjacent to exactly $$k$$ vertices that form a $$k$$-clique in $$H$$.
• No other graphs are $$k$$-trees.

This definition is a slightly modified version of the definition from Pinar Heggernes' lecture notes.

• Yes, my bad for the mistake in $k-1$ degree. (And thanks for the latexing demonstration!) Sep 21, 2010 at 5:12
• The other difference is the requirement that the neighbourhood be a clique. Sep 21, 2010 at 8:37
• @Andras: By "I basically agree with you", I actually meant that I agree that the first definition in the question is incorrect (as it does not require the neighborhood of $v$ to be a clique), and that the second definition in the question is almost correct, as "degree $k-1$" should be replaced with "degree $k$". Sep 21, 2010 at 15:34
• Ah, that makes more sense -- thanks for clarifying. Sep 21, 2010 at 15:58
• According to your definition, a complete graph on $k$ vertices is a $k$-tree, whose tree-width is $k-1$. However, to the best of my knowledge, a $k$-tree is the maximal graph with tree-width $k$, which implies that a $k$-clique would be a $(k-1)$-tree Aug 5, 2019 at 1:57