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

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

*Discrete Mathematics*,

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