Decomposition of Cubic Graphs on the Torus and Klein Bottle

Abstract

It was conjectured by Hoffman-Ostenhof that the edge set of every cubic graph can be decomposed into a spanning tree, a matching, and a family of cycles. This conjecture was verified for many graphs such as the Peterson graph, prisms over cycles, and Hamiltonian graphs. Later the conjecture was also verified for 3-connected cubic graphs on the plane and protective plane by Kenta Ozeki and Dong Ye. In this paper we will verify the conjecture for 3-connected cubic graph on the torus and Klein bottle.