Packings and Coverings of a Graph with 6 Vertices and 7 Edges

Abstract:

      Let $\lambda{K_v}$ be the complete multigraph with $v$ vertices and $G$ a finite simple graph. A $G$-design ($G$-packing design, $G$-covering design) of $\lambda {K_v}$, denoted by ($v,G,\lambda$)-$GD$ (($v,G,\lambda$)-$PD$, ($v,G,\lambda$)-$CD$), is a pair ($X,\cal B$) where $X$ is the vertex set of ${K_v}$ and $\cal B$ is a collection of subgraphs of ${K_v}$, called blocks, such that each block is isomorphic to $G$ and any two distinct vertices in ${K_v}$ are joined in exactly (at most, at least) $\lambda$ blocks of ${\cal B}$. A packing (covering) design is said to be maximum (minimum) if no other such packing (covering) design has more (fewer) blocks. In this paper, a simple graph $G$ with 6 vertices and 7 edges is discussed, and the maximum $G$-$PD(v)$ and the minimum $G$-$CD(v)$ are constructed for all orders $v$.