Further results on existentially closed graphs arising from block designs

DOI10.1007/S00373-019-02036-ZMaRDI QIDQ2287728zbMATH OpenOpenAlexWikidataFDO

Authors Xiao-Nan Lu

Publication date 21 January 2020

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.07719

zbMATH Keywords

block intersection graphexistential closurepairwise balanced designSteiner quadruple systemtriple system

Mathematics Subject Classification ID

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

Abstract: A graph is $n$-existentially closed ($n$-e.c.) if for any disjoint subsets $A$, $B$ of vertices with $|AcupB|=n$, there is a vertex $zotinAcupB$ adjacent to every vertex of $A$ and no vertex of $B$. For a block design with block set $calB$, its block intersection graph is the graph whose vertex set is $calB$ 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 $lambdage2$ 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 the necessary and sufficient conditions for such graphs to be $2$-e.c. are established.

Recommendations

• Existentially closed BIBD block-intersection graphs
• Existential closure of block intersection graphs of infinite designs having infinite block size
• Steiner triple systems and existentially closed graphs
• Existential closure of block intersection graphs of infinite designs having finite block size and index
• Graphs with the n-e.c. adjacency property constructed from affine planes

Cites work

• Allgemeine Schnittzahlen in t-Designs. (General intersection numbers in t-designs)
• Asymmetric graphs
• Classification algorithms for codes and designs
• Embeddings of simple triple systems
• Existential closure of block intersection graphs of infinite designs having finite block size and index
• Existential closure of block intersection graphs of infinite designs having infinite block size
• Existentially closed BIBD block-intersection graphs
• Graphs which contain all small graphs
• Graphs with the n-e.c. adjacency property constructed from affine planes
• Hadamard matrices and strongly regular graphs with the 3-e. c. adjacency property
• scientific article; zbMATH DE number 3926934 (Why is no real title available?)
• scientific article; zbMATH DE number 124518 (Why is no real title available?)
• scientific article; zbMATH DE number 1314686 (Why is no real title available?)
• scientific article; zbMATH DE number 2061960 (Why is no real title available?)
• scientific article; zbMATH DE number 1382770 (Why is no real title available?)
• scientific article; zbMATH DE number 3351594 (Why is no real title available?)
• scientific article; zbMATH DE number 3407679 (Why is no real title available?)
• Köhler theory for countable quadruple systems
• On an adjacency property of almost all graphs
• On Quadruple Systems
• On the adjacency properties of paley graphs
• On the existence of 2-designs Slambda(2,3,v) without repeated blocks
• Paley graphs satisfy all first-order adjacency axioms
• Properties of the Steiner triple systems of order 19
• Steiner quadruple systems - a survey
• Steiner triple systems and existentially closed graphs
• The CRC handbook of combinatorial designs
• The random graph
• The search for N-e.c. Graphs

Cited in

(7)

• Existentially closed BIBD block-intersection graphs
• Steiner triple systems and existentially closed graphs
• Existential closure of block intersection graphs of infinite designs having finite block size and index
• Existential closure of block intersection graphs of infinite designs having infinite block size
• Mutual incidence matrix of two balanced incomplete block designs
• Existential closure in line graphs
• More on block intersection polynomials and new applications to graphs and block designs

This page was built for publication: Further results on existentially closed graphs arising from block designs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2287728)