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.

enter image description here


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.

Source : Link , Question Author : A.Schulz , Answer Author : George Shakan

Leave a Comment