Six-cycle trades and a lower bound on the trade volumes of weakly connected graphs

Abstract

A C₆-trade consists of two disjoint decompositions of some simple graph H into copies of C₆. The number of vertices of H is referred to as the foundation of the trade, while the number of copies of C ₆ in each of the decompositions is called the volume of the trade. We determine the values of v and s for which there exists a C₆-trade of volume s and foundation v. We also present a more general result giving a lower bound for the trade volumes of various weakly connected graphs (including paths and cycles).