Convexity in Graphs and Hypergraphs

1986/07/01 by Martin Farber, Robert E. Jamison · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Graph theory and applications #Mathematics #Convexity #Chordal graph #Combinatorics #Discrete mathematics #Polyomino #Graph #Regular polygon #Geometry

paper · doi:10.1137/0607049

openalex publication_date 1986/07/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11

Abstract

We study several notions of abstract convexity in graphs and hypergraphs. In each case, we obtain analogues of several classical results, including the Minkowski–Krein–Milman theorem, Caratheodory’s theorem and Tietze’s convexity theorem. In addition, our results yield new characterizations of the classes of chordal gaphs, strongly chordal graphs, Ptolemaic graphs and totally balanced hypergraphs.

Citations

• Meet-distributive lattices and the anti-exchange closure

Cited by

• Convex sets in graphs, II. Minimal path convexity
• Geodetic Set on Graphs of Constant Pathwidth and Feedback Vertex Set Number
• Antimatroid [wikipedia]