Randomly Decomposable Multigraphs And Equipackable Multigraphs

Decomposing and packing are main contents in graph theory which have signifi-cance in network designing、theory of combinatorics optimization、crystallography、ope-rational research. Multigraph is one of the main studied objects of graph theory, and it is also an active area of research in graph theory. Some results about multigraphs which play an important role can be applied to computer networks, intelligent trans-portation and communication. There are many decomposing and packing problems in graph theory. In this paper, we investigate randomly H-decomposable multigraphs and H-equipackable multigraphs. A graph M is called a multigraph if M contains a loop or has two edges joining two common vertices. Let H be a fixed subgraph of a multigraph M. M is called randomly H-decomposable if every set of edge disjoint sub-graphs each isomorphic to H can be extended to a decomposition of M. An H-packing in M with l copies H1, H2,…, Hl of H is called maximal if M-lUi=1E(Hi) contains no subgraph isomorphic to H. An H-packing in M with l copies H1,H2,…,Hl of H is called maximum if no more than l edge disjoint copies of H can be packed into M. A multigraph M is called H-equipackable if every maximal H-packing in M is also a maximum H-packing in M. Randomly P3-decomposable simple graphs, Randomly P4-decomposable simple graphs, P3-equipackable simple graphs have been characterized. Firstly, All randomly P3-decomposable multigraphs and Randomly P4-decomposable multigraphs are characterized. Then, P3-equipackable multigraphs are characterized.