Simple Graphoidal Covers in a Graph

Abstract

A simple graphoidal cover of a graph $G$ is a collection $\psi$ of (not necessarily open) paths in $G$ such that every path in $\psi$ has at least two vertices, every vertex of $G$ is an internal vertex of at most one path in $\psi$, every edge of $G$ is in exactly one path in $\psi$, and any two paths in $\psi$ have at most one vertex in common. The minimum cardinality of a simple graphoidal cover of $G$ is called the simple graphoidal covering number of $G$ and is denoted by ${\eta }_s(G)$. In this paper, we determine the value of ${\eta }_s$ for several families of graphs. We also obtain several bounds for ${\eta }_s$ and characterize graphs attaining the bounds.