Steiner triple systems and existentially closed graphs (Q2571285)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Steiner triple systems and existentially closed graphs
scientific article

    Statements

    Steiner triple systems and existentially closed graphs (English)
    0 references
    1 November 2005
    0 references
    A graph is \(n\)-existentially closed if, for every \(n\)-subset \(S\) of the vertex set, for every subset \(T\) of \(S\), there is at least one vertex not in \(S\) adjacent to all vertices in \(T\) but none in \(S \setminus T\). When is the block intersection graph of a Steiner triple system of order \(v\) (STS\((v)\)) an \(n\)-existentially closed graph? It is proved that a block intersection graph of an STS\((v)\) is 2-existentially closed if and only if \(v \geq 13\). Turning to 3-existentially closed block intersection graphs, all orders except for \(v \in \{19,21\}\) are ruled out. It is shown that at least two STS(19)s have block intersection graphs that are 3-existentially closed; the case \(v=21\) is not resolved.
    0 references
    block intersection graph
    0 references
    0 references
    0 references
    0 references

    Identifiers