Geodesic
\( \mathcal{P} \)-Apex Graphs
Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 2, pp. 323-349

Voir la notice de l'article provenant de la source Library of Science

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 𝒫_r-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 𝒞 ( 𝒫 (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 
@article{DMGT_2018_38_2_a0,
     author = {Borowiecki, Mieczys{\l}aw and Drgas-Burchardt, Ewa and Sidorowicz, El\.zbieta},
     title = {\( {\mathcal{P}} {\)-Apex} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {323--349},
     publisher = {mathdoc},
     volume = {38},
     number = {2},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2018_38_2_a0/}
}
TY  - JOUR
AU  - Borowiecki, Mieczysław
AU  - Drgas-Burchardt, Ewa
AU  - Sidorowicz, Elżbieta
TI  - \( \mathcal{P} \)-Apex Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2018
SP  - 323
EP  - 349
VL  - 38
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2018_38_2_a0/
LA  - en
ID  - DMGT_2018_38_2_a0
ER  - 
%0 Journal Article
%A Borowiecki, Mieczysław
%A Drgas-Burchardt, Ewa
%A Sidorowicz, Elżbieta
%T \( \mathcal{P} \)-Apex Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2018
%P 323-349
%V 38
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2018_38_2_a0/
%G en
%F DMGT_2018_38_2_a0
Borowiecki, Mieczysław; Drgas-Burchardt, Ewa; Sidorowicz, Elżbieta. \( \mathcal{P} \)-Apex Graphs. Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 2, pp. 323-349. http://geodesic.mathdoc.fr/item/DMGT_2018_38_2_a0/