9
$\begingroup$

Treewidth is a graph parameter measuring how close a graph is to being a tree. I am interested in what is the minimal number of edges required for a graph to have treewidth $k$.

A natural family of graphs to consider are the cliques: a clique on $k+1$ vertices has treewidth $k$, and has $k (k+1) / 2$ edges. However, asymptotically, there are graphs of treewidth $k$ whose number of edges is linear rather than quadratic, e.g., cubic expanders as mentioned in this question. So cliques are not optimal. My question is: what is the smallest example of a graph of treewidth $k$ having less edges than the $(k+1)$-clique?

I have checked experimentally that all graphs of 14 edges or less have treewidth at most 4, so they do not beat the 6-clique which has 15 edges and treewidth 5. Hence, the smallest treewidth for which I do not know the answer is 6. Specifically: the 7-clique has 21 edges and treewidth 6, but is there a graph of treewidth 6 having 20 edges or less?

(Note that we could ask the same question of the minimal number of vertices required for a graph to have treewidth $k$, but then it is uninteresting: you need $k+1$ vertices for a graph to have treewidth $k$, and this is achieved by the $(k+1)$-clique.)

$\endgroup$
2
  • 2
    $\begingroup$ Related: having treewidth of $O(n)$ where $n$ is the number of vertices is known to be equivalent to having large expansion and bounded degree, see [1, Theorem 8]. The probabilistic construction of expanders would give you a graph with treewidth $k$ with $O(k)$ vertices whp. [1] Böttcher, Julia, et al. "Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs." European Journal of Combinatorics 31.5 (2010) $\endgroup$
    – holf
    Commented Jan 24 at 12:36
  • $\begingroup$ Re the previous comment. The quantifiers are not quite correct I believe. $\Omega(1)$ vertex expansion suffices for $\Omega(n)$ treewidth. And there exist bounded degree graphs (in particular degree 3) with $\Omega(1)$ vertex expansion. Edge and vertex expansion are related by the maximum degree, and hence one obtains vertex expansion automatically from edge expansion if degree is fixed (such as 3). $\endgroup$ Commented Jan 24 at 23:09

1 Answer 1

7
$\begingroup$

The smallest such example that is known to the House of Graphs is for $k = 9$. There is a graph of tree-width $9$ having only $44$ edges (while the $10$-clique contains $45$ edges).

$\endgroup$
1
  • $\begingroup$ Interesting, thanks! I'd be curious to know if this is "minimal" -- what about the smallest number of edges required for treewidth 6, 7, 8. $\endgroup$
    – a3nm
    Commented May 26 at 12:49

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.