Multipacking and Multicovering of K_n - F with Graph-Pairs of Order 5 where F is a Hamilton Cycle or an (almost) 1-Factor

摘要

A graph-pair of order t is two non-isomorphic graphs G and H on t non-isolated vertices for which G ∪ H ≈ K_t for some integer t ≥ 4. Given a graph-pair (G, H), we say (G, H) divides some graph K if the edges of K can be partitioned into copies of G and H with at least one copy of G and at least one copy of H. Such partition is called a (G,H)-multidecomposition of K. Whenever the multidecomposition is not feasible, we look for maximum multipacking and minimum multicovering.rnIn this paper, we consider the existence of multipacking and multicovering of K_n ― F with graph-pairs of order 5 where F is a Hamiltonian cycle or (almost) 1-factor.