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.

enter image description here

  • 3
    $\begingroup$ This is a great question; don't know why it hasn't received more attention or upvotes. $\endgroup$
    – joriki
    Dec 12 '12 at 10:10
  • 2
    $\begingroup$ 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. $\endgroup$
    – mjqxxxx
    Dec 13 '12 at 18:28
  • $\begingroup$ 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. $\endgroup$
    – Alexander Gruber
    Dec 19 '12 at 2:40
  • $\begingroup$ @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. $\endgroup$ May 27 '13 at 3:47
  • $\begingroup$ 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 $\endgroup$
    – jp26
    Jan 27 '14 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.


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.