14
$\begingroup$

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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
19
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 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, 2010 at 1:33
10
$\begingroup$

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)

Improve this answer
$\endgroup$
1
  • $\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, 2010 at 3:17

Your Answer

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

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