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/

[1] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, 2008).

[2] M. Borowiecki and P. Mihók, Hereditary properties of graphs, in: V.R. Kulli, Ed., Advances in Graph Theory (Vishawa International Publication Gulbarga, 1991).

[3] S. Cichacz, A. Görlich, M. Zwonek and A. Żak, On ( Cn; k ) stable graphs, Electron J. Combin. 18 (2011) #P205.

[4] E. Drgas-Burchardt, Forbidden graphs for classes of split-like graphs, European J. Combin. 39 (2014) 68–79. doi:10.1016/j.ejc.2013.12.004

[5] E. Drgas-Burchardt, On prime inductive classes of graphs, European J. Combin. 32 (2011) 1317–1328. doi:10.1016/j.ejc.2011.05.001

[6] A. Dudek, A. Szymański and M. Zwonek, ( H, k ) stable graphs with minimum size, Discuss. Math. Graph Theory 28 (2008) 137–149. doi:10.7151/dmgt.1397

[7] A. Dudek and M. Zwonek, ( H, k ) stable bipartite graphs with minimum size, Discuss. Math. Graph Theory 29 (2009) 573–581. doi:10.7151/dmgt.1465

[8] A. Dudek and A. Żak, On vertex stability with regard to complete bipartite subgraphs, Discuss. Math. Graph Theory 30 (2010) 663–669. doi:10.7151/dmgt.1521

[9] S. Dziobak, Excluded-minor characterization of apex-outerplanar graphs, PhD Thesis (Louisiana State Univ., 2011).

[10] J.-L. Fouquet, H. Thuillier, J.-M. Vanherpe and A.P. Wojda, On ( Kq ; k ) vertex stable graphs with minimum size, Discrete Math. 312 (2012) 2109–2118. doi:10.1016/j.disc.2011.04.017

[11] J.-L. Fouquet, H. Thuillier, J.-M. Vanherpe and A.P. Wojda, On (Kq; k) stable graphs with small k, Electron. J. Combin. 19 (2012) #P50.

[12] P. Frankl and G.Y. Katona, Extremal k-edge-Hamiltonian hypergraphs, Discrete Math. 308 (2008) 1415–1424. doi:10.1016/j.disc.2007.07.074

[13] T. Gallai, Transitiv orientierbare Graphen, Acta Math. Academiae Scientiarum Hungaricae 18 (1967) 25–66. doi:10.1007/BF02020961

[14] V. Giakoumakis, On the closure of graphs under substitution, Discrete Math. 177 (1997) 83–97. doi:10.1016/S0012-365X(96)00358-5

[15] A. Gyárfás, J. Lehel and Zs. Tuza, Upper bound on the order of τ-critical hyper-graphs, J. Combin. Theory Ser. B 33 (1982) 161–165. doi:10.1016/0095-8956(82)90065-X

[16] I. Horváth and G.Y. Katona, Extremal P 4 - stable graphs, Discrete Appl. Math. 159 (2011) 1786–1792. doi:10.1016/j.dam.2010.11.016

[17] J.M. Lewis and M. Yannakakis, The node-deletion problem for hereditary properties is NP-complete, J. Comput. System Sci. 20 (1980) 219–230. doi:10.1016/0022-0000(80)90060-4

[18] B. Mohar, Face covers and the genus problem for apex graphs, J. Combin. Theory Ser. B 82 (2001) 102–117. doi:10.1006/jctb.2000.2026

[19] N. Robertson and P. Seymour, Graph minors XX. Wagner’s conjecture, J. Combin. Theory Ser. B 92 (2004) 325–357. doi:10.1016/j.jctb.2004.08.001

[20] D.M. Thilikos and H.L. Bodlaender, Fast partitioning l-apex graphs with applications to approximating maximum induced-subgraph problems, Inform. Process. Lett. 61 (1997) 227–232. doi:10.1016/S0020-0190(97)00024-0

[21] Zs. Tuza, Critical hypergraphs and intersecting set-pair systems, J. Combin. Theory, Ser. B 39 (1985) 134–145. doi:10.1016/0095-8956(85)90043-7

[22] H. Whitney, Congruent graphs and the connectivity of graphs, Amer. J. Math. 54 (1932) 150–168. doi:10.2307/2371086

[23] A. Żak, On (Kq; k)-stable graphs, J. Graph Theory 74 (2013) 216–221. doi:10.1002/jgt.21705