Decomposition of graphs into paths and cycles

Summary: A decomposition of a graph \(G\) is a collection \(\psi\) of edge-disjoint subgraphs \(H_1,H_2,\ldots,H_r\) of \(G\) such that every edge of \(G\) belongs to exactly one \(H_i\). If each \(H_i\) is a path or a cycle in \(G\), then \(\psi\) is called a path decomposition of \(G\). If each \(H_i\) is a path in \(G\), then \(\psi\) 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 \(\pi(G)\) (\(\pi_a(G)\)). In this paper we initiate a study of the parameter \(\pi\) and determine the value of \(\pi\) for some standard graphs. Further, we obtain some bounds for \(\pi\) and characterize graphs attaining the bounds. We also prove that the difference between the parameters \(\pi\) and \(\pi_a\) can be made arbitrarily large.

Recommendations

Cites work

Cited in

(21)

This page was built for publication: Decomposition of graphs into paths and cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2249934)