Truly non-trivial graphoidal graphs

Abstract

A graphoidal cover of a graph G is a collection [Formula: see text] of non-trivial paths in G, which are not necessarily open, such that every vertex of G is an internal vertex of at most one path in [Formula: see text] and every edge of G is in exactly one path in [Formula: see text] If every path in a graphoidal [Formula: see text] of graph G has length at least 2, then graphoidal cover [Formula: see text] is called a truly non-trivial graphoidal cover (TNT graphoidal cover) of G. In this paper we obtain some structural necessary conditions for a graph to possess a TNT graphoidal cover. We also exhibit that these conditions are sufficient in the case of trees with diameter [Formula: see text] We also obtain a necessary condition in terms of order and size for a graph to possess a TNT graphoidal cover. Thereafter as an application of the necessary condition, we characterize complete graphs Kn and complete bipartite graphs [Formula: see text] possessing TNT graphoidal cover. Finally, we discuss regular graphs possessing TNT graphoidal cover and prove that every 3-regular graph possesses such a graphoidal cover.

Keywords

• Graphoidal cover
• truly non-trivial graphoidal cover
• graphoidal covering number
• 05C70
• 20D60