Packings and coverings of λKv by k-circuits with one chord

Abstract Let λK v be the complete multigraph with v vertices, where any two distinct vertices x and y are joined by λ edges { x , y }. Let G be a finite simple graph. A G -packing design ( G -covering design) of λK v , denoted by ( v , G , λ )-PD (( v , G , λ )-CD) is a pair (X, B ) , where X is the vertex set of 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) λ blocks of 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, the discussed graphs are C k ( r ) , i.e., one circle of length k with one chord, where r is the number of vertices between the ends of the chord, 1⩽ r k /2⌋. We give a unified method to construct maximum C k ( r ) -packings and minimum C k ( r ) -coverings. Especially, for G = C 6 ( r ) ( r =1,2), C 7 ( r ) ( r =1,2) and C 8 ( r ) ( r =1,2,3), we construct the maximum ( v , G , λ )-PD and the minimum ( v , G , λ )-CD.