TY - JOUR
T1 - Vertex- and edge-minimal and locally minimal graphs
AU - Boros, Endre
AU - Gurvich, Vladimir
N1 - Funding Information: This research was partially supported by DIMACS, Center for Discrete Mathematics and Theoretical Computer Science, Rutgers University, and by Graduate School of Information Science and Technology, University of Tokyo; the second author gratefully acknowledges also the partial support of Aarhus University Research Foundation and Center of Algorithmic Game Theory.
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 - https://doi.org/10.1016/j.disc.2008.10.020
DO - https://doi.org/10.1016/j.disc.2008.10.020
M3 - Article
VL - 309
SP - 3853
EP - 3865
JO - Discrete Mathematics
JF - Discrete Mathematics
SN - 0012-365X
IS - 12
ER -