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 \leq i \leq 9\).