Premium
Saturated graphs with minimal number of edges
Author(s) -
Kászonyi L.,
Tuza Zs.
Publication year - 1986
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190100209
Subject(s) - combinatorics , mathematics , cograph , disjoint sets , pairwise comparison , discrete mathematics , graph , 1 planar graph , chordal graph , statistics
Let F = { F 1 ,…} be a given class of forbidden graphs. A graph G is called F‐saturated if no F i ∈ F is a subgraph of G but the addition of an arbitrary new edge gives a forbidden subgraph. In this paper the minimal number of edges in F‐saturated graphs is examined. General estimations are given and the structure of minimal graphs is described for some special forbidden graphs (stars, paths, m pairwise disjoint edges).