2
$\begingroup$

Setup: Consider a graph $G := (V,E)$, with $|V|=\mathcal V, |E|=\mathcal E$ for notational simplicity.

We define the arboricity $\mathcal A$ of $G$ to be the minimum number of forests (acyclic graphs) we may decompose $G$ into. (This means each subgraph in the decomposition must be edge-disjoint, though vertices may repeat. Each subgraph cannot be cyclic.) $ \newcommand{\nc}{\newcommand} \newcommand{\A}{\mathcal{A}} \newcommand{\ceil}[1]{\left\lceil #1 \right\rceil} \newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor} \newcommand{\V}{\mathcal{V}} \newcommand{\E}{\mathcal{E}} \newcommand{\C}{\mathcal{C}} $

What is a graph $G$ where

$$\A \ne \ceil{ \frac{\E}{\V-1} }?$$

(Preferably a case where $G$ and the forests/trees it decomposes into are all nontrivial in nature, and are simple graphs. By "trivial," I exclude the case of a forest consisting entirely of just a pair of adjacent vertices, an isolated vertex, or an empty graph. Equivalently, a nontrivial forest - if I can get it to work - would be one with as many edges as vertices minus one, and at least 3 vertices.)


My Thoughts So Far: I've tried a fair number of examples with no real luck, but I have had some thoughts.

  • If $G$ is acyclic, then $\A$ is trivially just $1$, and conversely. Moreover, if $G$ acyclic means $\E = \V-1$. Therefore, we want to look at graphs which contain cycles instead.

  • Hence, any given forest taking up $n$ vertices will require $n-1$ edges. In particular, the maximum size for a forest subgraph of $G$ is $\E-1$ edges.

  • Suppose that $\A=2$. Then we want $\C$ (defined to be our ceiling function) to be at least $3$ ($1$ won't do it as noted previously). Thus we'll need $\E > 2\V - 2$.

  • In such a case, $\V \ge 5$ (since $K_4$ has $6$ edges).

  • Per MathWorld...

    • $G$ planar gives $\A \le 3$
    • $G$ being $k$-regular gives $\A = \floor{n/2}+1$ (though I think this is possibly a typo?)
    • $G = K_n$ has $\A = \ceil{n/2}$
    • $G = K_{m,n}$ has $\displaystyle \A = \ceil{ \frac{mn}{m+n-1} }$

But honestly, the more and more examples I try, the more and more I get lost. I'll try a decomposition, and so many times be one edge off from achieving $\A$ to be the desired number. Increasing $\C$ would only seem to make things worse and more complicated.

Maybe there's some fundamental misunderstanding I'm having (doesn't help that I'm new to graph theory), because it doesn't feel like it should be this difficult. Can anyone give me some help? Even just a nudge or idea would help a lot.

$\endgroup$
3
  • $\begingroup$ You may find some useful observations here or here $\endgroup$
    – kabenyuk
    Sep 15, 2021 at 11:57
  • $\begingroup$ I suspect that the arboricity of a $d$-regular graph is supposed to be $\lfloor \frac d2\rfloor + 1$, not $\lfloor \frac n2\rfloor + 1$ or for that matter the $\lceil \frac n2 \rceil + 1$ you've written. This always matches $\lceil \frac{\mathcal E}{\mathcal V-1}\rceil$, since a $d$-regular graph has $\frac12 nd$ edges. $\endgroup$ Sep 15, 2021 at 14:03
  • $\begingroup$ Yeah I was wondering about that since it felt weird for it to be independent of the degree, but I wasn't certain. (I'm more inclined to think I'm wrong than someone who knows this stuff.) $\endgroup$ Sep 15, 2021 at 19:05

1 Answer 1

2
$\begingroup$

The Nash-Williams formula for arboricity gives $$\mathcal A = \max_{H} \left\lceil \frac{\mathcal E_H}{\mathcal V_H - 1}\right\rceil$$ where the maximum is over all subgraphs $H$ of $G$ with at least $2$ vertices. So we just want to find a graph where the best $H$ to take is not all of $G$.

This can be obtained by starting with a very dense graph (which has very high arboricity for its number of vertices) and adding lots of vertices with very few new edges.

If you're fine with disconnected graphs, then it is easy to get $\frac{\mathcal E}{\mathcal V - 1}$ as low as you want without changing the arboricity. Simply start with $K_{10}$ (which has $10$ vertices, $45$ edges, and arboricity $5$) and add $36$ isolated vertices. The resulting graph has $46$ vertices and $45$ edges, so $\frac{\mathcal E}{\mathcal V-1} = 1$... but it still has arboricity $5$.

If you think this is silly and want a connected graph, you will have to do a bit more work, and you will not be able to get the arboricity below $2$, but you can still use the same idea: just add lots of new vertices to a dense graph, and the bare minimum number of edges to make it connected.

$\endgroup$

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.