On 4-connected 4-regular graphs without even cycle decompositions

摘要

An even cycle decomposition of a graph is a partition of its edges into even cycles. Markstrom constructed infinitely many 2-connected 4-regular graphs without even cycle decompositions. Macajova and Mazak then constructed an infinite family of 3-connected 4-regular graphs without even cycle decompositions. In this note, we further show that there exists an infinite family of 4-connected 4-regular graphs without even cycle decompositions. (C) 2022 Elsevier B.V. All rights reserved.