Graphs with Unique Minimum Simple Acyclic Graphoidal Cover

Abstract

A simple acyclic graphoidal cover of a graph $G$ is a collection $\psi$ of 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 acyclic graphoidal cover of $G$ is called the simple acyclic graphoidal covering number of $G$ and is denoted by ${\eta }_{as}(G)$. A simple acyclic graphoidal cover $\psi$ of $G$ with $|\psi |={\eta }_{as}(G)$ is called a minimum simple acyclic graphoidal cover of $G$. Two minimum simple acyclic graphoidal covers ${\psi }_1$ and ${\psi }_2$ of $G$ are said to be isomorphic if there exists an automorphism $\alpha$ of $G$ such that $\psi =\{\alpha (P):P\in {\psi }_1\}$. In this paper, we characterize trees, unicyclic graphs, and wheels in which any two minimum simple acyclic graphoidal covers are isomorphic.