4
$\begingroup$

Arboricity is defined by the minimal amount of forests required to partition the edges $E$ of a graph $G=(V,E)$.

I want to see what is the arboricity for certain graphs.

First, I look at the complete graph $K_n$. Knowing it has $\frac{n\cdot (n-1)}{2}$ edges, nd each forest may host up to $n-1$ edges, we can say that $\frac{n}{2}$ is a lower bound. But how can I show its an upper bound as well? Meaning, given a complete graph, in which way do i construct a forest decomposition using exactly $\frac{n}{2}$ forests?

Second, is in the case of planar graphs. I know by Nash-Williams equation that the arboricoty is $\max \frac{|E_H|}{|V_H|-1}$ over all induced subgraphs $H\subseteq G$. Additionally, for planar graphs I know that $|E|\leq 3•|V|-6$. But as the arboricity is the $\max$, and not the $\min$, I can't see how to combine those. I could read online that the arboricity of a planar graph cannot exceed $3$. But I dont see how I combine these things to prove it?

Finally, this is more of a general question. What is the relation between the arboricity of a graph and its maximal degree? Its easily showen that for any orientation given on $E$, the arboricity will be smaller or equal to the maximal outgoing degree. So the arboricoty is smaller or equal to the maximal degree, in the undirected scenario. But are there no tighter bounds? Or inequalities?

$\endgroup$
2
  • 1
    $\begingroup$ For $2n$ vertices, the complete graph is the union of $n$ zigzag Hamiltonian paths. Arrange the vertices in a circle. Half the path starts (a,a+1,a-1,a+2,...) The other half starts on the other side of the circle at (n+a,n+a+1,n+a-1,...) until they meet at a diameter. $\endgroup$
    – Empy2
    Aug 19, 2021 at 9:16
  • $\begingroup$ ...and for $2n + 1$ vertices you can take a star around a vertex and $n$ zigzag Hamiltonian paths covering the complete graph induced by the rest of the vertices. $\endgroup$
    – Dániel G.
    Aug 19, 2021 at 13:39

1 Answer 1

1
$\begingroup$

For the first two questions we can use the Nash-Williams equation you mention. In the case of a complete graph, the induced subgraphs are complete as well, so we have

$$\frac{|E_H|}{|V_H|-1} = \frac{\binom{|V_H|}{2}}{|V_H| - 1} =\frac{|V_H| (|V_H| - 1)}{2(|V_H| - 1)} = \frac{|V_H|}{2},$$

so $$\max \left\lceil\frac{|E_H|}{|V_H|-1}\right\rceil = \left \lceil \frac{n}{2} \right \rceil.$$

For planar graphs the induced subgraphs are planar as well, so we have $$ \frac{|E_H|}{|V_H|-1} \leq \frac{3|V_H| - 6}{|V_H| - 1} \leq 3.$$

Finally, in general you can't give a better bound in terms of the maximum degree: a cycle has maximum degree $2$ and you need at least two forests to cover it. The same example shows that your argument for why the arboricity is at most the maximum degree does not work, since you can orient the cycle so that the maximum of the out-degrees is $1$. But the assertion is true and you can show it using the same Nash-Williams equation and the bound $|E_H| \leq \frac{\Delta}{2} |V_H|$, where $\Delta$ is the maximum degree.

$\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.