Existentially Closed BIBD Block-Intersection Graphs

McKay, Neil A. and Pike, David A. (2007) Existentially Closed BIBD Block-Intersection Graphs. Electronic Journal of Combinatorics , 14 (1). pp. 1-10. ISSN 1077-8926

	[English] PDF (Migrated (PDF/A Conversion) from original format: (application/pdf)) - Published Version Available under License Creative Commons Attribution Non-commercial. Download (162kB) [English] PDF - Published Version Available under License Creative Commons Attribution Non-commercial. (Original Version)

Abstract

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.

Actions (login required)

View Item