88
$\begingroup$

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
    This is a great question; don't know why it hasn't received more attention or upvotes.2012-12-12
  • 2
    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.2012-12-13
  • 0
    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.2012-12-19
  • 0
    @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](http://webfile.ru/6536808)” 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.2013-05-27
  • 0
    A related question is that of Linear Arboricity, but the results for it are based upon the maximum degree of vertices. See for instance http://www.mimuw.edu.pl/~kowalik/papers/LinearArboricity.pdf2014-01-27
  • 0
    Note that $\sigma(\mathcal{P})/m$ is not the average path length, but its inverse.2014-02-08
  • 0
    Have you tried to look at a necklace of squares in which each square (4-cycle) is connected to its 2 neighbors by edges going out from 2 opposite vertices?2014-05-27
  • 0
    For $m$ isolated edges you need $m$ paths...2014-05-29
  • 0
    Isn't the icosahedron graph at least an example where $m/6$ paths is not enough? This has $m=30$ but requires at least $6$ paths.2014-05-29
  • 0
    @EinarRødland: I oversimplified and made an estimation with $3|V|$ edges instead of $3|V|-6$ edges. If you use the later bound you get $m/6 + 1$ paths (as for the icosahedron or tetrahedron). Still my main question is, whether the degree constraint is the only constraint for a path cover.2014-05-30
  • 0
    @A.Schulz: OK, that resolves that case. In order to be true for the regular triangle, it is required that the simple path be allowed to be a cycle: these seems to be some variation in how _simple path_ is defined.2014-05-30

1 Answers 1