# Number of simple edge-disjoint paths needed to cover a planar graph

Let $G=(V,E)$ be a graph with $|E|=m$ of a graph class $\mathcal{G}$. A path-cover $\mathcal{P}=\{P_1,\ldots,P_k\}$ is a partition of $E$ into edge-disjoint simple paths. The size of the cover is $\sigma(\mathcal{P})=k$. I am interested in upper and lower bounds for the quantity

$$\max_{G\in \mathcal{G}} \quad \min_{\mathcal{P} \text{ is path-cover of G}} \sigma(\mathcal{P})/m.$$

In other words, how large is the inverse of the average path length in the smallest path-cover in the worst case.

The graphs classes $\mathcal{G}$ I am interested in are (1) planar 3-connected graphs, and (2) triangulations.

There is a simple observation for a lower bound: In every odd-degree vertex one path has to start/end. So when all vertices have odd degree there any path-cover needs at least $m/6+1$ paths (a triangulation has $3|V|-6$ edges). You get the same result by noticing, that $(n-1)/2$ paths have to pass through a vertex of degree $n-1$.

Is a path-cover with $\frac{m}{6}$ paths always possible for planar graphs?

I am aware of a few results covering planar graphs with paths of length $3$.

Here is an example of a path-cover of the graph of the icosahedron.

-
This is a great question; don't know why it hasn't received more attention or upvotes. –  joriki Dec 12 '12 at 10:10
I don't understand the lower bound. Since a triangulation has $m=3n-6$ edges, a triangulation with all odd-degree vertices requires at least $n/2=(m+6)/6=m/6+1$ paths. For instance, $K_4$ needs $2$ (not $1$) paths to cover it. –  mjqxxxx Dec 13 '12 at 18:28
I am not sure if I would be able to do it, but somebody should try generating a big list of $\sigma(\mathcal{P})$'s for a bunch of the graphs in question. Maybe some data will help us see a pattern. –  Alexander Gruber Dec 19 '12 at 2:40
@A.Schulz Maybe the lower bound $m/6$ is weak for some classes of graphs. For instance, for the wheel graphs $W_n$, consisting of the cycle of length $n-1$ and the additional center vertex joined with all vertices of the cycle. Also there are Moon-Moser graphs $T_k$ (see Section 2 of the article “Long Cycles in 3-Connected Graphs” by Guantao Chen and Xingxing Yu), having no cycles of length greater than $(7/2) n^{\log_3 2}$. Maybe these graphs also have no small path-covers. –  Alex Ravsky May 27 '13 at 3:47
A related question is that of Linear Arboricity, but the results for it are based upon the maximum degree of vertices. See for instance mimuw.edu.pl/~kowalik/papers/LinearArboricity.pdf –  jp26 Jan 27 at 21:26

I will show that $\frac{m}{6}$ is not enough for 3-connected planar graphs. The following is inspired by fedja's comment (and also some nice discussion with Krystal Guo).

Consider the prism graph, which we will denote $P_n$. We say it has $2n$ vertices and $3n$ edges. Then in this case $\frac{m}{6} = \frac{n}{2}$. We will show that $\sigma(P_n) =n$. It is clear that $n$ paths is enough.

Consider the following graphs which we denote $T_n$:

and so on.. Note that $T_n$ has $3n - 1$ edges and $2n+2$ vertices.

It is not too hard to show that $\sigma(T_n) = n+1$ (and this is the best possible). One can show by induction, considering the left most edge between the upper and lower paths.

Let $p_1 , \ldots , p_k$ be a path cover of $P_n$. Now $P_n$ is two copies of $C_n$ with a matching, $M$, in between them. If every $e \in M$ is actually some $p_i$, then we have $k \geq n+2$.

So we may assume there is a $e = (u,v)$ such that the path, $p_i$, that contains $e$, contains at least one more edge, wolog say $(v,w)$.

$(i)$ The vertex $u$ is also contained in another edge of $p_i$ (other than $e$). Then $(V(P_n) , E(P_n) \setminus E(p_i))$ is $T_n$ minus at most two paths (actually, exactly two: the two paths start with precisely the two edges incident to $e$, respectively). In this case $k \geq n+1 - 2 + 1 = n$ (the last $+1$: don't forget to count $p_i$).

$(ii)$ The vertex $u$ is not contained in any other edge of $p_i$. Then let $p_j$ be another path that contains $u$. Then $(V(P_n) , E(P_n) \setminus (E(p_i)\cup E(p_j))$ is a $T_n$ minus at most 3 paths ($p_i$ is one path in $T_n$ and $p_j$ is at most two paths in $T_n$). It follows that $k \geq n + 1 - 3 +2= n$.

Thus we obtain $\sigma(P_n) = n$, as desired.

-