0
$\begingroup$

The $k$-vertex complete graph, $K_k$, is a $k$-tree. A $k$-tree with $n+1$ vertices $(n \geq k)$ is constructed from a $k$-tree on $n$ vertices by adding a vertex adjacent to all vertices of one of its $K_k$ subgraphs, and only to those vertices.

Is there an algorithm to recognize whether a graph is a k-tree? What is its time complexity? Are there efficient algorithms for special cases, particularly for k = 2, 3, 4, etc.?

$\endgroup$

1 Answer 1

1
$\begingroup$

Two facts:

  • The $k$-trees are exactly the chordal graphs where every maximal clique has $k+1$ vertices and every minimal separator has $k$ vertices (or it's $K_k$ or $K_{k+1}$)
  • In chordal graphs, the maximal cliques and the minimal separators can be enumerated in linear time (see e.g. this paper)

In conclusion, there is a linear time algorithm for recognizing $k$-trees, for any $k$.

$\endgroup$
1
  • $\begingroup$ Good! By the way, it is possible to recognize chordal graphs in linear time. $\endgroup$
    – licheng
    Jul 30, 2023 at 8:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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