𝒫-Apex Graphs
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 approa...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2018-05-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.2041 |
| _version_ | 1797718029769900032 |
|---|---|
| author | Borowiecki Mieczysław Drgas-Burchardt Ewa Sidorowicz Elżbieta |
| author_facet | Borowiecki Mieczysław Drgas-Burchardt Ewa Sidorowicz Elżbieta |
| author_sort | Borowiecki Mieczysław |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-12T08:45:02Z |
| format | Article |
| id | doaj.art-9b8d94ffc9354ed18ae7953a0eab2035 |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T08:45:02Z |
| publishDate | 2018-05-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-9b8d94ffc9354ed18ae7953a0eab20352023-09-02T16:29:33ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922018-05-0138232334910.7151/dmgt.2041dmgt.2041𝒫-Apex GraphsBorowiecki Mieczysław0Drgas-Burchardt Ewa1Sidorowicz Elżbieta2Faculty of Mathematics, Computer Science and Econometrics, University of Zielona Góra, Prof. Z. Szafrana 4a, 65–516Zielona Góra, PolandFaculty of Mathematics, Computer Science and Econometrics, University of Zielona Góra, Prof. Z. Szafrana 4a, 65–516Zielona Góra, PolandFaculty of Mathematics, Computer Science and Econometrics, University of Zielona Góra, Prof. Z. Szafrana 4a, 65–516Zielona Góra, PolandLet 𝒫 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.https://doi.org/10.7151/dmgt.2041induced hereditary classes of graphsforbidden subgraphshypergraphstransversal number05c7505c15 |
| spellingShingle | Borowiecki Mieczysław Drgas-Burchardt Ewa Sidorowicz Elżbieta 𝒫-Apex Graphs Discussiones Mathematicae Graph Theory induced hereditary classes of graphs forbidden subgraphs hypergraphs transversal number 05c75 05c15 |
| title | 𝒫-Apex Graphs |
| title_full | 𝒫-Apex Graphs |
| title_fullStr | 𝒫-Apex Graphs |
| title_full_unstemmed | 𝒫-Apex Graphs |
| title_short | 𝒫-Apex Graphs |
| title_sort | 𝒫 apex graphs |
| topic | induced hereditary classes of graphs forbidden subgraphs hypergraphs transversal number 05c75 05c15 |
| url | https://doi.org/10.7151/dmgt.2041 |
| work_keys_str_mv | AT borowieckimieczysław papexgraphs AT drgasburchardtewa papexgraphs AT sidorowiczelzbieta papexgraphs |