Variable neighborhood search for extremal graphs. 5. Three ways to automate finding conjectures Original Research Article

Let λKv 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 λKv, denoted by (v,G,λ)-PD ((v,G,λ)-CD) is a pair (X,B), where X is the vertex set of Kv and B is a collection of subgraphs of Kv, called blocks, such that each block is isomorphic to G and any two distinct vertices in Kv 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 Ck(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 Ck(r)-packings and minimum Ck(r)-coverings. Especially, for G=C6(r)(r=1,2), C7(r)(r=1,2) and C8(r)(r=1,2,3), we construct the maximum (v,G,λ)-PD and the minimum (v,G,λ)-CD.