15

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?

Artem Kaznatcheev
  • 10,251
  • 12
  • 74
  • 174
ethkim
  • 151
  • 1
  • 3
  • 6
    Could you latex-ify your question - makes it easier to read. See http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/237#237 for more details – Suresh Venkat Sep 21 '10 at 08:06
  • With this definition ,I can not draw a 2_tree,will you please draw and send it for me? –  Apr 19 '15 at 13:06

1 Answers1

17

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.

Serge Gaspers
  • 5,116
  • 29
  • 42
  • The other difference is the requirement that the neighbourhood be a clique. – András Salamon Sep 21 '10 at 08: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$". – Serge Gaspers Sep 21 '10 at 15:34
  • Ah, that makes more sense -- thanks for clarifying. – András Salamon Sep 21 '10 at 15:58
  • Yes, my bad for the mistake in $k-1$ degree. (And thanks for the latexing demonstration!) – ethkim Sep 21 '10 at 05:12
  • 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 – Mengfan Ma Aug 05 '19 at 01:57
  • Indeed, I corrected this to start from the (k+1)-clique as a base case. – Serge Gaspers Nov 13 '19 at 12:34