a Department of Mathematics, Manonmaniam Sundaranar University, Tirunelveli 627 012, India
b Department of Mathematics, Loyola College, Chennai 600 034, India
c Department of Mathematics, D.B. Jain College, Chennai 600 096, India
Abstract:
An acyclic graphoidal cover of a graph G is a collection ψ of paths in G such that every path in ψ has at least two vertices, every vertex of G is an internal vertex of at most one path in ψ and every edge of G is in exactly one path in ψ. The minimum cardinality of an acyclic graphoidal cover of G is called the acyclic graphoidal covering number of G and is denoted by ηa. In this paper we characterize the class of graphs G for which ηa=Δ−1 where Δ is the maximum degree of a vertex in G.