Pack Graphs with Subgraphs of Size Three

Abstract

An H -packing F of a graph G is a set of edge -disjoint subgraphs of G in which each subgraph is isomorphic to H. The leave L or the remainder graph L of a packing F is the subgraph induced by the set of edges of G that does not occur in any subgraph of the packing F. If a leave L contains no edges, or simply L = Phi, then G is said to be H -decomposable, denoted by H broken vertical bar G. In this paper, we prove a conjecture made by Chartrand, Saba and Mynhardt [13]: If G is a graph of size q(G) 0 (mod 3) and delta(G) >= 2, then G is H -decomposable for some graph H of size 3.