错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Existential Closure in Line Graphs

  • Andrea C. Burgess,
  • Robert D. Luther,
  • David A. Pike

摘要

A graph is n-existentially closed if, for all disjoint sets of vertices A and B with \(|A\cup B|=n\) | A B | = n , there is a vertex z not in \(A\cup B\) A B 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 five 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.