Acyclic graphoidal covers and path partitions in a graph

✍ Scribed by S. Arumugam; J. Suresh Suseela

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 436 KB
• Volume: 190
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/s0012-365x(98)00032-6

✦ Synopsis

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 aeyclie graphoidal covering number of G and is denoted by ~/a. A path partition of a graph G is a collection ~ of paths in G such that every edge of G is in exactly one path in ~. The minimum cardinality of a path partition of G is called the path partition number of G and is denoted by lr. In this paper we determine ~/a and ~ for several classes of graphs and obtain a characterization of all graphs with A ~< 4 and ~/a = d --1. We also obtain a characterization of all graphs for which ~/a = ~.