Vertex- and edge-minimal and locally minimal graphs

Endre Boros, Vladimir Gurvich

Research output: Contribution to journalArticle

6 Citations (Scopus)

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

Fingerprint

Directed graphs
Graph in graph theory
Vertex of a graph
Directed Graph
Perfect Graphs
Minimality
Imperfect
kernel
Partially Ordered Set
Induced Subgraph
Subgraph
Odd

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

Cite this

Boros, Endre ; Gurvich, Vladimir. / Vertex- and edge-minimal and locally minimal graphs. In: Discrete Mathematics. 2009 ; Vol. 309, No. 12. pp. 3853-3865.
@article{0107c863285b41a9983b10168818d2a0,
title = "Vertex- and edge-minimal and locally minimal graphs",
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.",
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",
author = "Endre Boros and Vladimir Gurvich",
year = "2009",
month = "6",
day = "28",
doi = "10.1016/j.disc.2008.10.020",
language = "English (US)",
volume = "309",
pages = "3853--3865",
journal = "Discrete Mathematics",
issn = "0012-365X",
publisher = "Elsevier",
number = "12",

}

Vertex- and edge-minimal and locally minimal graphs. / Boros, Endre; Gurvich, Vladimir.

In: Discrete Mathematics, Vol. 309, No. 12, 28.06.2009, p. 3853-3865.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Vertex- and edge-minimal and locally minimal graphs

AU - Boros, Endre

AU - Gurvich, Vladimir

PY - 2009/6/28

Y1 - 2009/6/28

N2 - 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.

AB - 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.

KW - Chromatic number

KW - Clique number

KW - Complementary connected graphs

KW - Kernel

KW - Locally edge-minimal

KW - Locally vertex-minimal

KW - Odd anti-holes

KW - Odd holes

KW - Perfect and imperfect graphs

KW - Rotterdam graphs

UR - http://www.scopus.com/inward/record.url?scp=67349189523&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=67349189523&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2008.10.020

DO - 10.1016/j.disc.2008.10.020

M3 - Article

AN - SCOPUS:67349189523

VL - 309

SP - 3853

EP - 3865

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 12

ER -