Consider a $k$ regular graph of $n$ vertices, where $3 \leq k \leq (n-1)$. Is there any upper or lower bound, in the worst case, known for either the tree-width or the clique width of each $k$ regular family?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
For each $k$-regular family, the treewidth and cliquewidth can be both $\Theta(n)$, due to the existence of expanders.
By On Balanced Separators, Treewidth, and Cycle Rank Thm. 2.1, $tw(G) \geq \tilde s(G) -1$, and by the definition of the strict balanced separator number, $\tilde s(G)$ is at least the size of a balanced separator of a graph. A random regular graph is an expander, which in turn makes the size of balanced separators $\Theta(n)$. Thus $tw(G)=\Theta(n)$.
By The Tree-Width of Clique-Width Bounded Graphs without $K_{n,n}$, every graph of clique-width $k$ which does not contain the complete bipartite graph $K_{n,n}$ for some $n > 1$ as a subgraph has tree-width at most $3k(n − 1) − 1$. It's possible to take $n=3$ for random regular graphs, thus the clique-width is also $\Theta(n)$.
answered Sep 14, 2022 at 2:08
-
$\begingroup$ Is there a reference to the fact that no random regular graph has $K_{3 \times 3}$ as a subgraph? Also, for what regularity does this fact break down? It is obviously false for a complete ($n-1$ regular graph), because the tree width of a complete graph is linear, but the clique width is bounded. It is also false for $n-2$ and $n-3$ regular graphs for a similar reason. Is it true from $n-4$ regular graphs? $\endgroup$ Commented Sep 15, 2022 at 5:16
-
1$\begingroup$ @RandomMatrices It's true for n-4 regular graphs. As the complement of an (n-4)-regular graph is a cubic graph, and the complement graph of a graph of clique-width k has clique-width at most 2k, the (n-4)-regular graph has clique-width Θ(n) if the cubic graph is taken to be a random cubic graph. $\endgroup$ Commented Sep 15, 2022 at 5:24
-
1$\begingroup$ The reference for $K_{3,3}$ is N. C. Wormald's survey, Models of random regular graphs, Lemma 2.7. The lemma states that for fixed d and fixed graph F with more edges than vertices, almost all random d-regular graphs do not contain F as a subgraph. $\endgroup$ Commented Sep 15, 2022 at 5:27