Packings and Coverings of \(\lambda K_v\) by the Graphs with Seven Points, Seven Edges and One \(5\)-Circle

Abstract

Let \(\lambda K_v\) be the complete multigraph with \(v\) vertices, where any two distinct vertices \(x\) and \(y\) are joined by \(\lambda\) edges \(\{x,y\}\). Let \(G\) be a finite simple graph. A \(G\)-packing design (\(G\)-covering design) of \(K_v\), denoted by \((v,G,\lambda)\)-PD (\((v,G,\lambda)\)-CD) is a pair \((X,B)\), where \(X\) is the vertex set of \(\lambda K_v\) and \(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 at most (at least) \(\lambda\) blocks of \(B\). A packing (covering) design is said to be maximum (minimum) if no other such packing (covering) design has more (fewer) blocks. There are four graphs with 7 points, 7 edges and a 5-circle, denoted by \(G_i\), \(i = 1,2,3,4\). In this paper, we have solved the existence problem of the maximum \((v, G_i,\lambda)\)-PD and the minimum \((v, G_i, \lambda)\)-CD.