Finding a graph where the arboricity does not equal a certain ceiling function

Question

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.

Answer 1

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.