Symmetric graph designs (Q1972324)

The authors introduce the notion of a symmetric graph design (SGD) which is a generalization of a symmetric balanced incomplete block design. In particular, a symmetric \((n,G,\lambda;F)\)-design is a collection \(\{G_1, G_2, \dots{}, G_n\}\) of spanning subgraphs of the complete graph \(K_n\) such that: (i) \(G_i \simeq G\) for \(i = 1, \dots{}, n\); (ii) every edge of \(K_n\) is contained in exactly \(\lambda\) subgraphs \(G_i\), and (iii) \(G_i \cap G_j \simeq F\) for all \(i, j, i \neq j\), and \(|E(F)|= \lambda' = {{\lambda}\choose{2}}\). The paper consists of a series of results on existence of various families of SGDs. Just some of the results will be summarized here. Trivially every symmetric \((v,k,\lambda)\)-BIBD is a \((v,K_k,\lambda)\)-SGD. A further trivial example is an \((n,K_{n-1},n-2; K_{n-2})\)-SGD which exists for all \(n\). For \(\lambda = 1\) an \((n,G,1)\)-SGD is an edge-disjoint decomposition of \(K_n\) into copies of \(G\) where \(G\) is a spanning subgraph with \((n-1)/2\) edges. When \(\lambda = 2\) an \((n,G,2)\)-SGD is an orthogonal double cover (ODC) of \(K_n\) by \(G\), and such objects have been well studied. For \(\lambda = 3\) the authors ask for which pairs \(G\), \(F\) does there exist an \((n,G,3;F)\)-SGD? Although it appears hopeless to determine the spectrum in the general case, the authors do give some results for the more restricted question where \(F \simeq K_3\). They show that if there exists an \((n,k,1)\)-BIBD then there exists an \((n,G_{r,k-1},k-2; K_{k-2})\)-SGD where \(r = (n-1)/(k-1)\), and \(G_{r,t}\) is the graph with \(rt+1\) vertices and \(r+1\) components, \(r\) of which are \(K_t\) and one is \(K_1\). As a corollary an \((n,G_{(n-1)/4,4},3;K_3)\)-SGD exists for all \(n \equiv 1,5 \pmod{20}\). But the question of whether an \((n,G_{(n-1)/4,4},3;K_3)\)-SGD exists for the remaining values of \(n \equiv 1 \pmod{4}\) remains open. By analogy with the well-known result on ODCs the authors conjecture that for all \(k \geq 4\) there exists a constant \(n_0\) such that an \((n,G_{(n-1)/(k-1),k-1},k-2; K_{k-2})\)-SGD exists for all \(n \equiv 1 \pmod{k-1}\), \(n \geq n_0\). If \(F_{r,k}\) is the connected graph with \(r(k-1)+1\) vertices consisting of \(r\) copies of \(K_k\) glued together at a single common vertex, the authors show that an \((n,F_{r,k},k;K_k)\)-SGD (where \(r = (n-1)/(k-1)\)) exists if and only if there exists an \((n,k,1)\)-BIBD. Following a PBD-closure result for rooted SGDs, the authors then establish the triplication result that if there exists an \((n,G,3;K_3)\)-SGD then there exists a \((3n,G^*,3;K_3)\)-SGD where \(G^*\) is the graph on \(3n\) vertices obtained from the \(n\)-vertex graph \(G\) by appending at each vertex a triangle with two new vertices, one of which is common to all appended triangles. This leads to the following generalization. Let \(G\) be an \(n\)-vertex graph, and suppose there exists a \((n,G,t';K_t)\)-SGD. If there exists a transversal design \(\text{TD}(2t,n)\) then there exists a \((tn,G^{(t)},t;K_t)\)-SGD. Finally the authors show that if \(n\) is a prime power and \(F\) is a graph with \({n+1}\choose{2}\) edges which has a \(\rho\)-labelling, then there exists an \((n^2+n+1,G,n+1;F)\)-SGD for some graph \(G\) with \((n+1){{n+1}\choose{2}}\) edges.