On primal graphs with maximum degree 2 (Q2875908)

Primal graphs are graphs such that every graph is either primal or has an edge-decomposition into non-isomorphic primal graphs. For example, the graphs \(2^iK_2\), \(2^iK_{1,2}\), \(C_5+K_2\) and \(7C_5+K_2\) are primal. The authors define a new parameter, which determines how far a graph is from having an edge-decomposition into graphs of the form \(2^iK_2\) and those of the form \(2^iK_{1,2}\), and show that graphs with a small value of this parameter can be edge-decomposed into non-isomorphic graphs of the form \(2^iK_2\), \(2^iK_{1,2}\), \(C_5+K_2\) and \(7C_5+K_2\).