Research On Some Kinds Of Equipacking And Equicovering Problems

Packing and covering are main contents in graph theory which have significance in network designing、theory of combinatorics optimization、crystallography、operational research. Packing and covering are dual properties of graphs, which play important roles in researching structures and other properties of graphs. There are many packing and covering problems in graph theory. Equipacking and equicovering problems are one kind of dual packing and covering problems. In this paper, we investigate H-equipackable and H-equicoverable graphs. An H-packing in G with l copies H1, H2,…, Hl of H is called maximal if G—(?) E(Hi) contains no subgraph isomorphic to H. An H-packing in G with l copies H1, H2,…, Hl of H is called maximum if no more than l edge dis-joint copies of H can be packed into G. A graph G is called H-equipackable if every maximal H-packing in G is also a maximum H-packing in G. An H-covering of G with l copies H1, H2,…, Hl of H is called minimal if, for any(?) E(Hi)-E(Hj) is not an H-covering of G. An H-covering of G with l copies H1, H2,…, Hl of H is called minimum if there exists no H-covering with less than l copies H. A graph is called H-equicoverable if every minimal H-covering in G is also a minimum H-covering in G.P3-equipackable graphs, M2-equipackable graphs, P3-equicoverable graphs, M2-equicoverable graphs have been characterized. Firstly, Mk-equipackable graph-s are characterized, based on M3-decomposable graphs, randomly M3-decomposable graphs, and M2-equipackable graphs. Secondly, Mk-equipackable paths and cycles, Pk-equipackable paths and cycles, Pm∪Pk-equipackable paths and cycles are char-acterized. Finally, Mk-equicoverable paths and cycles, Pk-equicoverable paths and cycles, Pm∪Pk-equicoverable paths and cycles are characterized.