Graphs with unique minimum acyclic graphoidal cover – I
S. Arumugam, Indra Rajasingh, P. Roushini Leely Pushpam · Journal of Discrete Mathematical Sciences and Cryptography · 2004
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.