Decomposition of Graphs into Cycles of Length Seven and Single Edges

Teresa Sousa1
1CMA and Departamento de Matematica Faculdade de Ciéncias e Tecnologia Universidade Nova de Lisboa 2829-516 Caparica, Portugal

Abstract

Given graphs \(G\) and \(H\), an \(H\)-decomposition of \(G\) is a partition of the edge set of \(G\) such that each part is either a single edge or forms a graph isomorphic to \(H\). Let \(\gamma_H(n)\) denote the smallest number \(k\) such that any graph \(G\) of order \(n\) admits an \(H\)-decomposition with at most \(k\) parts. Here, we study the case when \(H = C_7\), the cycle of length \(7\), and prove that \(\gamma_{C_7}(n) = \left\lceil \frac{nZ^2}{4} \right\rceil\) for all \(n \geq 10\).