Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2018
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/1810.07719 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916940536086528 |
|---|---|
| author | Lu, Xiao-Nan |
| author_facet | Lu, Xiao-Nan |
| contents | 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 $\cal B$, its block intersection graph is the graph whose vertex set is $\cal 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 $λ$-fold triple systems with $λ\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 the necessary and sufficient conditions for such graphs to be $2$-e.c. are established. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1810_07719 |
| institution | arXiv |
| publishDate | 2018 |
| record_format | arxiv |
| spellingShingle | Further Results on Existentially Closed Graphs Arising from Block Designs Lu, Xiao-Nan Combinatorics 05B07, 05B05, 05C75 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 $\cal B$, its block intersection graph is the graph whose vertex set is $\cal 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 $λ$-fold triple systems with $λ\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 the necessary and sufficient conditions for such graphs to be $2$-e.c. are established. |
| title | Further Results on Existentially Closed Graphs Arising from Block Designs |
| topic | Combinatorics 05B07, 05B05, 05C75 |
| url | https://arxiv.org/abs/1810.07719 |