Packings and coverings of λKv by k-circuits with one chord
✍ Scribed by Qingde Kang; Yanfang Zhang; Huijuan Zuo
- Publisher
- Elsevier Science
- Year
- 2004
- Tongue
- English
- Weight
- 322 KB
- Volume
- 279
- Category
- Article
- ISSN
- 0012-365X
No coin nor oath required. For personal study only.
✦ Synopsis
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 ÿnite 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 C (r) k , i.e., one circle of length k with one chord, where r is the number of vertices between the ends of the chord, 1 6 r ¡ k=2 . We give a uniÿed method to construct maximum C (r) k -packings and minimum C (r) k -coverings. Especially, for G = C (r) 6 (r = 1; 2), C (r) 7 (r = 1; 2) and C (r) 8 (r = 1; 2; 3), we construct the maximum (v; G; )-PD and the minimum (v; G; )-CD.