| Summary: | Let ๐ซ be an arbitrary class of graphs that is closed under taking induced subgraphs and let ๐ (๐ซ) be the family of forbidden subgraphs for ๐ซ. We investigate the class ๐ซ (k) consisting of all the graphs G for which the removal of no more than k vertices results in graphs that belong to ๐ซ. This approach provides an analogy to apex graphs and apex-outerplanar graphs studied previously. We give a sharp upper bound on the number of vertices of graphs in ๐ (๐ซ (1)) and we give a construction of graphs in ๐ (๐ซ (k)) of relatively large order for k โฅ 2. This construction implies a lower bound on the maximum order of graphs in ๐ (๐ซ (k)). Especially, we investigate ๐ (๐ฒr(1)), where ๐ฒr denotes the class of Pr-free graphs. We determine some forbidden subgraphs for the class ๐ฒr(1) with the minimum and maximum number of vertices. Moreover, we give sufficient conditions for graphs belonging to ๐(๐ซ (k)), where ๐ซ is an additive class, and a characterisation of all forests in C(๐ซ (k)). Particularly we deal with ๐(๐ซ (1)), where ๐ซ is a class closed under substitution and obtain a characterisation of all graphs in the corresponding ๐(๐ซ (1)). In order to obtain desired results we exploit some hypergraph tools and this technique gives a new result in the hypergraph theory.
|
|---|