On Graphs Whose Acyclic Graphoidal Covering Number Is One Less than Its Cyclomatic Number

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 an exactly one path in $\psi$. If further no member of $\psi$ is a cycle, then $\psi$ is called an acyclic graphoidal cover of $G$. The minimum cardinality of an acyclic graphoidal cover is called the acyclic graphoidal covering number of $G$ and is denoted by ${\eta }_a$. In this paper, we characterize the class of graphs for which ${\eta }_a=q–p$, where $p$ and $q$ denote respectively the order and size of $G$.