McKay, Neil A. and Pike, David A. (2007) Existentially Closed BIBD BlockIntersection Graphs. Electronic Journal of Combinatorics , 14 (1). pp. 110. ISSN 10778926
[English]
PDF (Migrated (PDF/A Conversion) from original format: (application/pdf))
 Published Version
Available under License Creative Commons Attribution Noncommercial. Download (158Kb)


Abstract
A graph G with vertex set V is said to be nexistentially 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 blockintersection 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 nonempty intersection. In this paper we study balanced incomplete block designs (BIBDs) and when their blockintersection graphs are nexistentially closed. We characterise the BIBDs with block size k ≥ 3 and index λ = 1 that have 2e.c. blockintersection graphs and establish bounds on the parameters of BIBDs with index λ = 1 that are ne.c. where n ≥ 3. For λ ≥ 2 and n ≥ 2, we prove that only simple λfold designs can have ne.c. blockintersection graphs. In the case of λfold triple systems we show that n ≥ 3 is impossible, and we determine which 2fold triple systems (i.e., BIBDs with k = 3 and A = 2) have 2e.c. blockintersection graphs.
Item Type:  Article 

URI:  http://research.library.mun.ca/id/eprint/463 
Item ID:  463 
Keywords:  Block designs; Blockintersection graphs; Existentially closed graphs 
Department(s):  Science, Faculty of > Mathematics and Statistics 
Date:  16 October 2007 
Date Type:  Publication 
Actions (login required)
View Item 