Vertex- and edge-minimal and locally minimal graphs

Endre Boros, Vladimir Gurvich

Research output: Contribution to journalArticle

6 Scopus citations

Abstract

Given a family of graphs G, a graph G ∈ G is called edge-minimal (vertex-minimal) if G ∉ G for every subgraph (induced subgraph) G of G; furthermore, G is called locally edge-minimal (locally vertex-minimal) if G ∉ G whenever G is obtained from G by deleting an edge (a vertex). Similarly, the concepts of minimality and local minimality are introduced for directed graphs (digraphs) and, more generally, for partially ordered sets. For example, by the Strong Perfect Graph Theorem, the only vertex-minimal graphs with χ > ω are odd holes and anti-holes. In contrast, the only locally vertex-minimal graphs with χ > ω are partitionable graphs. Somewhat surprisingly, there are infinitely many non-trivial perfect graphs that are locally edge-minimal and -maximal simultaneously. In other words, such a graph is perfect but it becomes imperfect after any edge is deleted from or added to it. In this paper we consider vertex- and edge-minimal and locally minimal graphs in the following families: (i) perfect and imperfect graphs, (ii) graphs with χ = ω and with χ > ω, (iii) digraphs that have a kernel and kernel-free digraphs, and finally, (iv) vertex-minimal complementary connected d-graphs.

Original languageEnglish (US)
Pages (from-to)3853-3865
Number of pages13
JournalDiscrete Mathematics
Volume309
Issue number12
DOIs
StatePublished - Jun 28 2009

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Keywords

  • Chromatic number
  • Clique number
  • Complementary connected graphs
  • Kernel
  • Locally edge-minimal
  • Locally vertex-minimal
  • Odd anti-holes
  • Odd holes
  • Perfect and imperfect graphs
  • Rotterdam graphs

Fingerprint Dive into the research topics of 'Vertex- and edge-minimal and locally minimal graphs'. Together they form a unique fingerprint.

  • Cite this