A graph G with vertex set V is said to be n-existentially closed if, for every S ⊂ V with |S| = n and every T ⊆ S, there exists a vertex x ∈V - S such that x is adjacent to each vertex of T but is adjacent to no vertex of S -T. Given a combinatorial design D with block set B, its block-intersection graph GD is the graph having vertex set B such that two vertices b1 and b2 are adjacent if and only if b1 and b2 have non-empty intersection. In this paper we study balanced incomplete block designs (BIBDs) and when their block-intersection graphs are n-existentially closed. We characterise the BIBDs with block size k ≥ 3 and index λ = 1 that have 2-e.c. block-intersection graphs and establish bounds on the parameters of BIBDs with index λ = 1 that are n-e.c. where n ≥ 3. For λ ≥ 2 and n ≥ 2, we prove that only simple λ-fold designs can have n-e.c. block-intersection graphs. In the case of λ-fold triple systems we show that n ≥ 3 is impossible, and we determine which 2-fold triple systems (i.e., BIBDs with k = 3 and A = 2) have 2-e.c. block-intersection graphs.
展开▼
