Let G be a tree on 2n vertices. The treewidth of G, tw(G) = 1. Now suppose we add n edges to G to get a graph H. An easy upper bound on tw(H) is n + 1. Is this essentially the best possible?

It seems somehow that tw(H) should be O(sqrt(n)) , but this is just a vague hunch. Do we know better upper bounds than O(n) for the treewidth of a graph obtained by adding n edges to a tree on 2n vertices?


Your model is not really any less general than asking about arbitrary 3-regular graphs, and 3-regular expander graphs have linear treewidth. So I don't know about constant factors, but Θ(n) is best possible, yes.

  • 3
    $\begingroup$ Thanks, that answers my question. To elaborate David's answer a bit, let H be a connected 3-regular graph on 2n vertices. H then has 3n edges. Let G be a tree on 2n vertices obtained by removing n+1 edges from H. Adding n of these edges back to G will give us H' = (H minus one edge). Letting H be an expander graph with treewidth \theta(n), we see that H' has treewidth \theta(n) as well. $\endgroup$ – gphilip Aug 17 '10 at 1:33

As David pointed out, you basically ask for bounds on the treewidth of a connected graph with average degree 3. For the more special case of 3-regular graphs, the following lower and upper bounds can be obtained. Denoting by pw(G) the pathwidth of a graph G, it is clear that

(1) tw(G) <= pw(G) for any graph G (as a path decomposition is a tree decomposition)

It is proved in [1] that

(2) For every \epsilon > 0, there exists an integer n_0 such that for any 3-regular graph G on n >= n_0 vertices, pw(G) <= n/6 + \epsilon*n.

This gives you an upper bound of roughly n/6 on the treewidth of 3-regular graphs.

For an almost sure lower bound, I cite from [2]:

"As random cubic graphs almost surely have bisection width at least 0.101 n (Kostochka, Melnikov, 1992), they have almost surely no separator of size smaller than n/20" and thus almost surely no tree decomposition of width smaller than n/20.

For a "sure" lower bound on the bisection width, [3] showed an infinite family of 3-regular graphs, such that each graph G=(V,E) in this family has bisection width at least 0.082 * |V|.

[1] Fedor V. Fomin, Kjartan Høie: Pathwidth of cubic graphs and exact algorithms. Inf. Process. Lett. 97(5): 191-196 (2006)

[2] Jaroslav Nesetril, Patrice Ossona de Mendez: Grad and classes with bounded expansion II. Algorithmic aspects. Eur. J. Comb. 29(3): 777-791 (2008)

[3] Sergei L. Bezrukov, Robert Elsässer, Burkhard Monien, Robert Preis, Jean-Pierre Tillich: New spectral lower bounds on the bisection width of graphs. Theor. Comput. Sci. 320(2-3): 155-174 (2004)

  • $\begingroup$ Thank you, Serge. The bound via pathwidth is probably more accessible to me at this stage than the one via expander graphs; I haven't read either proof yet, though. $\endgroup$ – gphilip Aug 17 '10 at 3:17

Your Answer

