# 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 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$ 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 $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
show 1 more comment