The intersection problem for star designs (Q1377722): Difference between revisions

If \(G\) is a simple graph without isolated vertices, \(B\) is called a \(G\)-design if \(B\) is a finite set of graphs, each isomorphic to \(G\), with the property that for every pair \(u,v\) of vertices in the union of their vertex set, there is at most one graph in \(B\) of which \(uv\) is an edge. If \(H\) is the union of the graphs in \(B\), \(B\) is called a \(G\)-design on \(H\), so \(E(H)=| B| E(G)\). If \(B\) is a \(G\)-design on the complete graph \(K_n\), then \(B\) is called a \(G\)-design of order \(n\). The spectrum problem for \(G\) is the problem of determining Spec(\(G\)), the set of all \(n\) for which there is a \(G\)-design of order \(n\). The intersection problem for \(G\) is the problem of determining for all \(n\in \) Spec(\(G\)), the set of all \(k\) for which there are \(G\)-designs \(B_1\) and \(B_2\), on the same vertex set, with \(| B_1 \cap B_2| =k\). The authors determine those triples \((m,n,k)\) of integers for which there are two \(m\)-star designs on the same \(n\)-set having exacatly \(k\) stars in common.