4
$\begingroup$

Note $S_n$ the Sierpiński sieve graph of order $n$, which is obtained from the connectivity of the Sierpiński sieve.

S_n

For $n$ high enough, what is the treewidth of $S_n$?

I think that I can show that it is at least $4$ (by obtaining $K_5$ as a graph minor), and that it is at most $5$ (by obtained a tree-decomposition scheme involving bags of size $6$). My gut feeling is that it should be $5$, but I cannot find a proper database for forbidden minors at treewidth $4$ (and I can't access Sanders' thesis mentioned here).

$\endgroup$
14
$\begingroup$

You can recursively decompose each triangle into a smaller triangle and a trapezoid, and each trapezoid into two smaller triangles. The corresponding tree decomposition (whose bags contain the corners of a triangle at one level of the decomposition and a triangle or trapezoid at the next or previous level) has five vertices per bag and therefore has width four.

There is no $K_5$ minor, because the graph is planar. There is, however, a $K_{2,2,2}$ (octahedron) minor (actually, a subdivision), shown below. As this is one of the forbidden minors for treewidth three, the width is four.

enter image description here

$\endgroup$
  • $\begingroup$ Nice figure @David Eppstein. How did you draw it? $\endgroup$ – Chandra Chekuri Sep 6 '16 at 22:33
  • $\begingroup$ Adobe Illustrator, mostly using their click, drag and snap copying operation to repeatedly triple a single equilateral triangle. $\endgroup$ – David Eppstein Sep 6 '16 at 22:47
  • $\begingroup$ Thanks for the clear explanation! I should have realized that there can't be a $K_5$ since it is planar... $\endgroup$ – while False Sep 7 '16 at 0:44

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.