Two 6.9-edge Map Filling And Cover Design

A complete multigraph of order v and index A, denoted by λK_v, is an undirected graph with v vertices, where any two distinct vertices x and y are joined by A edges {x, y}. Let G be a finite simple graph. A graph design G-GDλ{v) ( graph packing design G-PDλ(v), graph covering design G-CDλ(v)) of XK_v 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 isomophic to G and any two distinct vertices in K_v are joined exactly (at most, at least) in A blocks of B. A packing (covering) design is said to be maximum (minimum) if no other such packing (covering) design of the same order has more (fewer) blocks. In this paper, the maximum packing design and the minimun covering design of two graphs with six vertices and nine edges are researched. By an unified method, we solve the problems of the maximum packing design and the minimum covering design for all possible v and A.In addition, the enumeration problem for nonnegative integer solutions of the equation x + ay + bz = n is discussed. And the unified enumeration formulas are obtained. Futhermore, a brief description of the formulas for the case a\b is given.