Decomposition of Graphs into Paths and Cycles

Abstract EN

A decomposition of a graph G is a collection ψ of edge-disjoint subgraphs H1,H2,…,Hr of G such that every edge of G belongs to exactly one Hi.

If each Hi is a path or a cycle in G, then ψ is called a path decomposition of G.

If each Hi is a path in G, then ψ is called an acyclic path decomposition of G.

The minimum cardinality of a path decomposition (acyclic path decomposition) of G is called the path decomposition number (acyclic path decomposition number) of G and is denoted by π(G) (πa(G)).

In this paper we initiate a study of the parameter π and determine the value of π for some standard graphs.

Further, we obtain some bounds for π and characterize graphs attaining the bounds.

We also prove that the difference between the parameters π and πa can be made arbitrarily large.