×

Further results on existentially closed graphs arising from block designs. (English) Zbl 1431.05023

Summary: A graph is \(n\)-existentially closed \((n\)-e.c.) if for any disjoint subsets \(A\), \(B\) of vertices with \(|A \cup B| = n\), there is a vertex \(z \notin A \cup B\) adjacent to every vertex of \(A\) and no vertex of \(B\). For a block design with block set \(\mathcal{B}\), its block intersection graph is the graph whose vertex set is \(\mathcal{B}\) and two vertices (blocks) are adjacent if they have non-empty intersection. In this paper, we investigate the block intersection graphs of pairwise balanced designs, and propose a sufficient condition for such graphs to be 2-e.c. In particular, we study the \(\lambda\)-fold triple systems with \(\lambda \ge 2\) and determine for which parameters their block intersection graphs are 1- or 2-e.c. Moreover, for Steiner quadruple systems, the block intersection graphs and their analogue called \(\{1\}\)-block intersection graphs are investigated, and necessary and sufficient conditions for such graphs to be 2-e.c. are established.

MSC:

05B05 Combinatorial aspects of block designs
05B07 Triple systems
05C75 Structural characterization of families of graphs

References:

[1] Ananchuen, W.; Caccetta, L., On the adjacency properties of Paley graphs, Networks, 23, 227-236 (1993) · Zbl 0777.05095 · doi:10.1002/net.3230230404
[2] Baker, CA; Bonato, A.; Brown, JMN, Graphs with the \(3\)-e.c. adjacency property constructed from affine planes, J. Combin. Math. Combin. Comput., 46, 65-83 (2003) · Zbl 1037.05011
[3] Baker, CA; Bonato, A.; Brown, JMN; Szőnyi, T., Graphs with the \(n\)-e.c. adjacency property constructed from affine planes., Discrete Math., 308, 901-912 (2008) · Zbl 1139.05064 · doi:10.1016/j.disc.2007.07.029
[4] Beth, T., Jungnickel, D., Lenz, H.: Design Theory Vol. 1, Encyclopedia Math. Appl., vol. 69, 2nd edn. Cambridge University Press, Cambridge (1999) · Zbl 0945.05005
[5] Blass, A.; Exoo, G.; Harary, F., Paley graphs satisfy all first-order adjacency axioms, J. Graph Theory, 5, 435-439 (1981) · Zbl 0472.05058 · doi:10.1002/jgt.3190050414
[6] Bollobás, B.; Thomason, A., Graphs which contain all small graphs, Eur. J. Combin., 2, 13-15 (1981) · Zbl 0471.05037 · doi:10.1016/S0195-6698(81)80015-7
[7] Bonato, A., The search for \(n\)-e.c. graphs, Contrib. Discrete Math., 4, 40-53 (2009) · Zbl 1203.05138
[8] Bonato, A.; Cameron, K., On an adjacency property of almost all graphs, Discrete Math., 231, 103-119 (2001) · Zbl 0973.05043 · doi:10.1016/S0012-365X(00)00309-5
[9] Bonato, A.; Holzmann, WH; Kharaghani, H., Hadamard matrices and strongly regular graphs with the \(3\)-e.c. adjacency property., Electron. J. Combin., 8, r1 (9pp) (2001) · Zbl 0955.05068
[10] Cameron, Peter J., The Random Graph, 333-351 (1997), Berlin, Heidelberg · Zbl 0864.05076
[11] Colbourn, C.J., Dinitz, J.H. (eds.): Handbook of Combinatorial Designs, 2nd edn. CRC Press, Boca Raton (2007) · Zbl 1101.05001
[12] Colbourn, CJ; Forbes, AD; Grannell, MJ; Griggs, TS; Kaski, P.; Östergård, PR; Pike, DA; Pottonen, O., Properties of the Steiner triple systems of order 19, Electron. J. Combin., 17, #r98 (2010) · Zbl 1193.05039
[13] Colbourn, C.J., Rosa, A.: Triple Systems. Oxford University Press, Oxford (1999) · Zbl 0938.05009
[14] Dehon, M., On the existence of \(2\)-designs \({S}_\lambda (2, 3, v)\) without repeated blocks, Discrete Math., 43, 155-171 (1983) · Zbl 0502.05008 · doi:10.1016/0012-365X(83)90153-X
[15] Erdős, P.; Rényi, A., Asymmetric graphs, Acta Math. Acad. Sci. Hungar., 14, 295-315 (1963) · Zbl 0118.18901 · doi:10.1007/BF01895716
[16] Forbes, A.; Grannell, MJ; Griggs, TS, Steiner triple systems and existentially closed graphs, Electron. J. Combin., 12, #r42 (2005) · Zbl 1075.05012
[17] Hanani, H., On quadruple systems, Can. J. Math, 12, 145-157 (1960) · Zbl 0092.01202 · doi:10.4153/CJM-1960-013-3
[18] Hartman, A., Phelps, K.T.: Steiner quadruple systems. In: J. Dinitz, D. Stinson (eds.) Contemporary Design Theory: A Collection of Surveys, chap. 6, pp. 205-240. Wiley, New York (1992) · Zbl 0765.05017
[19] Horsley, D.; Pike, DA; Sanaei, A., Existential closure of block intersection graphs of infinite designs having infinite block size, J. Combin. Des., 19, 317-327 (2011) · Zbl 1225.05035 · doi:10.1002/jcd.20283
[20] Kaski, P., Östergård, P.R.: Classification Algorithms for Codes and Designs, Algorithms Comput. Math., vol. 15. Springer, New York (2006) · Zbl 1089.05001
[21] Kaski, P., Östergård, P.R.: Extra material for “Classification Algorithms for Codes and Designs”. http://extras.springer.com/2006/978-3-540-28990-6/ (2006). Accessed 25 Feb 2019 · Zbl 1089.05001
[22] Kikyo, H.; Sawa, M., Köhler theory for countable quadruple systems, Tsukuba J. Math., 41, 189-213 (2017) · Zbl 1383.05029 · doi:10.21099/tkbjm/1521597622
[23] Köhler, E., Allgemeine Schnittzahlen in \(t\)-designs, Discrete Math., 73, 133-142 (1989) · Zbl 0683.05009
[24] Lindner, CC; Rosa, A., Steiner quadruple systems—a survey, Discrete Math., 22, 147-181 (1978) · Zbl 0398.05015 · doi:10.1016/0012-365X(78)90122-X
[25] Mathon, R.; Rosa, A., Tables of parameters of BIBDs with \(r\le 41\) including existence, enumeration, and resolvability results, Ann. Discrete Math, 26, 275-308 (1985) · Zbl 0579.05016
[26] McKay, NA; Pike, DA, Existentially closed BIBD block-intersection graphs, Electron. J. Combin., 14, #r70 (2007) · Zbl 1158.05011
[27] Mendelsohn, N.S.: Intersection numbers of \(t\)-designs. In: L. Mirsky (ed.) Studies in Pure Mathematics, pp. 145-150. Academic Press, London (1971) · Zbl 0222.05018
[28] Mendelsohn, NS; Hung, SHY, On the Steiner systems \(S(3,4,14)\) and \(S(4,5,15)\), Utilitas Math., 1, 5-95 (1972) · Zbl 0258.05017
[29] Pike, DA; Sanaei, A., Existential closure of block intersection graphs of infinite designs having finite block size and index, J. Combin. Des., 19, 85-94 (2011) · Zbl 1273.05186 · doi:10.1002/jcd.20271
[30] Piotrowski, W.: Notwendige Existenzbedingungen für Steinersysteme und ihre Verallgemeinerungen. Diplomarbeit Univ, Hamburg (1977)
[31] Shen, H., Embeddings of simple triple systems, Sci. China Ser. A, 35, 283-291 (1992) · Zbl 0776.05017
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.