𝒫-Apex Graphs

Abstract

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.

Keywords

• induced hereditary classes of graphs
• forbidden subgraphs
• hypergraphs
• transversal number
• 05c75
• 05c15