Existential Closure in Line Graphs

arXiv2211.01168MaRDI QIDQ6415935FDOQ6415935

Authors: Andrea Burgess, Robert D. Luther, David A. Pike 

Publication date: 2 November 2022

Abstract: A graph $G$ is {it $n$-existentially closed} if, for all disjoint sets of vertices $A$ and $B$ with $|AcupB|=n$, there is a vertex $z$ not in $AcupB$ adjacent to each vertex of $A$ and to no vertex of $B$. In this paper, we investigate $n$-existentially closed line graphs. In particular, we present necessary conditions for the existence of such graphs as well as constructions for finding infinite families of such graphs. We also prove that there are exactly two $2$-existentially closed planar line graphs. We then consider the existential closure of the line graphs of hypergraphs and present constructions for $2$-existentially closed line graphs of hypergraphs.

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Hypergraphs (05C65) Graph operations (line graphs, products, etc.) (05C76) Graph theory (05C99)

This page was built for publication: Existential Closure in Line Graphs

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