| Packings and Coverings of a Graph with 6 Vertices and 7 Edges |
| Received:October 29, 2006 Revised:March 23, 2007 |
| Key Words:
$G$-design $G$-packing design $G$-covering design.
|
| Fund Project:the National Natural Science Foundation of China (No.10671055). |
|
| Hits: 8234 |
| Download times: 2122 |
| Abstract: |
| Let $\lambda{K_v}$ be the complete multigraph with $v$ vertices and $G$ a finite simple graph. A $G$-design ($G$-packing design, $G$-covering design) of $\lambda {K_v}$, denoted by ($v,G,\lambda$)-$GD$ (($v,G,\lambda$)-$PD$, ($v,G,\lambda$)-$CD$), is a pair ($X,\cal B$) where $X$ is the vertex set of ${K_v}$ and $\cal 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 exactly (at most, at least) $\lambda$ blocks of ${\cal 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, a simple graph $G$ with 6 vertices and 7 edges is discussed, and the maximum $G$-$PD(v)$ and the minimum $G$-$CD(v)$ are constructed for all orders $v$. |
| Citation: |
| DOI:10.3770/j.issn:1000-341X.2008.04.007 |
| View Full Text View/Add Comment |
|
|
|
