Apex Graphs and Cographs
A class G of graphs is called hereditary if it is closed under taking induced subgraphs. We denote by G^{apex} the class of graphs G that contain a vertex v such that G − v is in G. Borowiecki, Drgas-Burchardt, and Sidorowicz proved that if a hereditary class G has finitely many forbidden induced su...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Georgia Southern University
2024-01-01
|
| Series: | Theory and Applications of Graphs |
| Subjects: | |
| Online Access: | https://digitalcommons.georgiasouthern.edu/tag/vol11/iss1/4/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1841560761399246848 |
|---|---|
| author | Jagdeep Singh Vaidy Sivaraman Thomas Zaslavsky |
| author_facet | Jagdeep Singh Vaidy Sivaraman Thomas Zaslavsky |
| author_sort | Jagdeep Singh |
| collection | DOAJ |
| description | A class G of graphs is called hereditary if it is closed under taking induced subgraphs. We denote by G^{apex} the class of graphs G that contain a vertex v such that G − v is in G. Borowiecki, Drgas-Burchardt, and Sidorowicz proved that if a hereditary class G has finitely many forbidden induced subgraphs, then so does G^{apex}. We provide an elementary proof of this result.
The hereditary class of cographs consists of all graphs G that can be generated from K_1 using complementation and disjoint union. A graph is an apex cograph if it contains a vertex whose deletion results in a cograph. Cographs are precisely the graphs that do not have the 4-vertex path as an induced subgraph. Our main result finds all such forbidden induced subgraphs for the class of apex cographs. |
| format | Article |
| id | doaj-art-2a57c486c5eb4b728029842e38ca4efb |
| institution | Kabale University |
| issn | 2470-9859 |
| language | English |
| publishDate | 2024-01-01 |
| publisher | Georgia Southern University |
| record_format | Article |
| series | Theory and Applications of Graphs |
| spelling | doaj-art-2a57c486c5eb4b728029842e38ca4efb2025-01-03T15:22:35ZengGeorgia Southern UniversityTheory and Applications of Graphs2470-98592024-01-0111110.20429/tag.2024.110104Apex Graphs and CographsJagdeep SinghVaidy SivaramanThomas ZaslavskyA class G of graphs is called hereditary if it is closed under taking induced subgraphs. We denote by G^{apex} the class of graphs G that contain a vertex v such that G − v is in G. Borowiecki, Drgas-Burchardt, and Sidorowicz proved that if a hereditary class G has finitely many forbidden induced subgraphs, then so does G^{apex}. We provide an elementary proof of this result. The hereditary class of cographs consists of all graphs G that can be generated from K_1 using complementation and disjoint union. A graph is an apex cograph if it contains a vertex whose deletion results in a cograph. Cographs are precisely the graphs that do not have the 4-vertex path as an induced subgraph. Our main result finds all such forbidden induced subgraphs for the class of apex cographs.https://digitalcommons.georgiasouthern.edu/tag/vol11/iss1/4/apex graphcographforbidden induced subgraph |
| spellingShingle | Jagdeep Singh Vaidy Sivaraman Thomas Zaslavsky Apex Graphs and Cographs Theory and Applications of Graphs apex graph cograph forbidden induced subgraph |
| title | Apex Graphs and Cographs |
| title_full | Apex Graphs and Cographs |
| title_fullStr | Apex Graphs and Cographs |
| title_full_unstemmed | Apex Graphs and Cographs |
| title_short | Apex Graphs and Cographs |
| title_sort | apex graphs and cographs |
| topic | apex graph cograph forbidden induced subgraph |
| url | https://digitalcommons.georgiasouthern.edu/tag/vol11/iss1/4/ |
| work_keys_str_mv | AT jagdeepsingh apexgraphsandcographs AT vaidysivaraman apexgraphsandcographs AT thomaszaslavsky apexgraphsandcographs |