Characterization of a class of graphs with unique minimum graphoidal cover

Abstract

A graphoidal cover of a graph $ G$ is a collection $ \psi$ of (not necessarily open) paths in $ G$ such that every vertex of $ G$ is an internal vertex of at most one path in $ \psi$ and every edge of $ G$ is in exactly one path in $ \psi$. The minimum cardinality of a graphoidal cover of $ G$ is called the graphoidal covering number of $ G$ and is denoted by $ \eta$ . Two graphoidal covers $ \psi_1$ and $ \psi_2$ of a graph $ G$ are said to be isomorphic if there exists an automorphism $ f$ of $ G$ such that $ \psi_2=\{f(P)/P\in \psi_1\}$. A graph $ G$ is said to have a unique minimum graphoidal cover if any two minimum graphoidal covers of $ G$ are isomorphic. In this paper we characterize the class of all graphs $ G$ with a unique minimum graphoidal cover when $ \delta=2$ and no end block of $ G$ is a cycle.