Randomly Decomposable Graphs And Equipackable Graphs

Decomposing and packing problems are very important and fundamental in graph theory. Not only they can be used to study the structural properties of graphs, but also they have a significant value in network design. There are many kinds of decom-posing and packing problems in graph theory. In this paper, we only study two kinds which have very close relation:the problems of characterizing randomly decomposable graphs and equipackable graphs. A graph G is called randomly H-decomposable if the H-decomposition of every H-decomosable subgraph of G can be extended to an H-decompositon of G. A graph G is called H-equipackable if every maximal H-packing in G is also a maximum H-packing in G. In this paper, we characterize all randomly P3 U P2-decomposable graphs, randomly C3-decomposable graphs and some kind of special P3 U P2-graphs, and transform the problem of C3-equipacking into other equivalent problems.