11
$\begingroup$

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 \ v$ is a $k$-tree.

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

Am I correct?

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

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$ vertices, or $G$ has a vertex $v$ with degree $k$ such that the (open) neighborhood of $v$ forms a $k$-clique, and $G \setminus 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$ vertices is a $k$-tree.
  • A $k$-tree $G$ with $n+1$ vertices ($n\ge k$) 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.

$\endgroup$
  • $\begingroup$ Yes, my bad for the mistake in $k-1$ degree. (And thanks for the latexing demonstration!) $\endgroup$ – ethkim Sep 21 '10 at 5:12
  • $\begingroup$ The other difference is the requirement that the neighbourhood be a clique. $\endgroup$ – András Salamon Sep 21 '10 at 8:37
  • $\begingroup$ @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$". $\endgroup$ – Serge Gaspers Sep 21 '10 at 15:34
  • $\begingroup$ Ah, that makes more sense -- thanks for clarifying. $\endgroup$ – András Salamon Sep 21 '10 at 15:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.