Six-Vertex Graph Packings and Coverings of \( \lambda K_v \)

Zhihe Liang1, Jianyong Wang2
1Department of Mathematics, Hebei Normal University Shijiazhuang 050016, P. R. China
2Department of Mathematics, Henan University Kaifeng 475000, P. R. China

Abstract

Let \( \lambda K_v \) be the complete multigraph, and \( G \) a finite simple graph. A \( G \)-design (\( G \)-packing, \( G \)-covering, respectively) of \( \lambda K_v \) is denoted by \( GD(v, G, \lambda) \) (\( PD(v, G, \lambda) \), \( CD(v, G, \lambda) \), respectively). In this paper, we will give some construction methods of graph packings and graph coverings, determine the existence spectrum for the \( G \)-designs of \( \lambda K_v \), and construct the maximum packings and the minimum coverings of \( \lambda K_v \) with \( G \) for any positive integer \( \lambda \). The graph \( G \) is either \( (K_4 – e) \cup P_1 \) or \( C_5 \bigodot P_1 \). Therefore, the problems of \( G \)-coverings and \( G \)-packings of \( \lambda K_v \) are solved completely when \( G \) is a graph with order \( 6 \) and \( |E(G)| \leq 6 \).

Keywords: G-design; G-packing; G-covering