- Tytuł:
- \( \mathcal{P} \)-Apex Graphs
- Autorzy:
-
Borowiecki, Mieczysław
Drgas-Burchardt, Ewa
Sidorowicz, Elżbieta - Powiązania:
- https://bibliotekanauki.pl/articles/31342421.pdf
- Data publikacji:
- 2018-05-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
induced hereditary classes of graphs
forbidden subgraphs
hypergraphs
transversal number - Opis:
- Let \( \mathcal{P} \) be an arbitrary class of graphs that is closed under taking induced subgraphs and let \( \mathcal{C}( \mathcal{P} ) \) be the family of forbidden subgraphs for \( \mathcal{P} \). We investigate the class \( \mathcal{P} (k) \) consisting of all the graphs \( G \) for which the removal of no more than \( k \) vertices results in graphs that belong to \( \mathcal{P} \). 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 \( \mathcal{C}( \mathcal{P}(1)) \) and we give a construction of graphs in \( \mathcal{C}( \mathcal{P}(k)) \) of relatively large order for \( k \ge 2 \). This construction implies a lower bound on the maximum order of graphs in \( \mathcal{C}( \mathcal{P}(k)) \). Especially, we investigate \( \mathcal{C}( \mathcal{W}_r(1)) \), where \( \mathcal{W}_r \) denotes the class of \( \mathcal{P}_r \)-free graphs. We determine some forbidden subgraphs for the class \( \mathcal{W}_r(1) \) with the minimum and maximum number of vertices. Moreover, we give sufficient conditions for graphs belonging to \( \mathcal{C} ( \mathcal{P} (k)) \), where \( \mathcal{P} \) is an additive class, and a characterisation of all forests in \( \mathcal{C} ( \mathcal{P} (k)) \). Particularly we deal with \( \mathcal{C} ( \mathcal{P} (1)) \), where \( \mathcal{P} \) is a class closed under substitution and obtain a characterisation of all graphs in the corresponding \( \mathcal{C} ( \mathcal{P} (1)) \). In order to obtain desired results we exploit some hypergraph tools and this technique gives a new result in the hypergraph theory.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2018, 38, 2; 323-349
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł