Let G be a graph of order p and size q. An acyclic graphoidal cover of G is a collection Ψ of internally disjoint and edge-disjoint paths in G covering all the edges of G. The acyclic graphoidal covering number ηa of G is the minimum cardinality of an acyclic graphoidal cover of G. Two acyclic graphoidal covers Ψ1 and Ψ2 of G are isomorphic if there exists an automorphism f of G such that Ψ2 = (f(P)/P ∈ Ψ1). In this paper we characterize the class of graphs of G with ηa > q–p in which any two minimum acyclic graphoidal covers are isomorphic. © 2004 Taylor & Francis Group, LLC.