### 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 language | English (US) |
---|---|

Pages (from-to) | 3853-3865 |

Number of pages | 13 |

Journal | Discrete Mathematics |

Volume | 309 |

Issue number | 12 |

DOIs | |

State | Published - Jun 28 2009 |

### Fingerprint

### 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

*Discrete Mathematics*,

*309*(12), 3853-3865. https://doi.org/10.1016/j.disc.2008.10.020

}

*Discrete Mathematics*, vol. 309, no. 12, pp. 3853-3865. https://doi.org/10.1016/j.disc.2008.10.020

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

Research output: Contribution to journal › Article

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 -