Symmetric graph designs
type: Item
instance of: scholarly article
title: Symmetric graph designs
zbMATH Open document ID: 0952.05005
published in: Graphs and Combinatorics
publication date: 2000-12-28T00:00:00Z
review text: 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 …
reviewed by: Peter B. Gibbons
Mathematics Subject Classification ID: 05B05
Mathematics Subject Classification ID: 51E05
zbMATH DE Number: 1436041
zbMATH Keywords: symmetric balanced incomplete block design
zbMATH Keywords: symmetric graph design
zbMATH Keywords: orthogonal double cover
author: Hans-Dietrich O. F. Gronau
author: Ronald C. Mullin
author: Alexander Rosa
author: Paul J. Schellenberg
MaRDI profile type: Publication
full work available at URL: s003730050006
OpenAlex ID: W2093541724
DOI: 10.1007/S003730050006
description: scientific article; zbMATH DE number 1436041