Graph Designs for Nine Graphs With Six Vertices and Nine Edges

Abstract

Let $K_v$ be the complete graph with $v$ vertices. Let $G$ be a finite simple graph. A $G$-decomposition of $K_v$, denoted by $G$-GD$(v)$, is a pair $(X,\mathcal{B})$ where $X$ is the vertex set of $K_v$, and $\mathcal{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 one block of $\mathcal{B}$. In this paper, nine graphs $G_i$ with six vertices and nine edges are discussed, and the existence of $G_i$-decompositions are completely solved, $1\le i\le 9$.