Forbidden paths and cycles in the undirected underlying graph of a 2-quasi best match graph
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913472012353536 |
|---|---|
| author | Korchmaros, Annachiara |
| author_facet | Korchmaros, Annachiara |
| contents | The undirected underlying graph of a 2-quasi best match graph (2-qBMG) is proven not to contain any induced graph isomorphic to $P_6$ or $C_6$. This new feature allows for the investigation of 2-BMGs further by exploiting the numerous known results on $P_6$ and $C_6$ free graphs together with the available polynomial algorithms developed for their studies. In this direction, there are also some new contributions about dominating bicliques and certain vertex decompositions of the undirected underlying graph of a 2-qBMG. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_09997 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Forbidden paths and cycles in the undirected underlying graph of a 2-quasi best match graph Korchmaros, Annachiara Combinatorics Discrete Mathematics 05C12 (Primary) 05C15, 05C57 (Secondary) G.2.2; G.2.3 The undirected underlying graph of a 2-quasi best match graph (2-qBMG) is proven not to contain any induced graph isomorphic to $P_6$ or $C_6$. This new feature allows for the investigation of 2-BMGs further by exploiting the numerous known results on $P_6$ and $C_6$ free graphs together with the available polynomial algorithms developed for their studies. In this direction, there are also some new contributions about dominating bicliques and certain vertex decompositions of the undirected underlying graph of a 2-qBMG. |
| title | Forbidden paths and cycles in the undirected underlying graph of a 2-quasi best match graph |
| topic | Combinatorics Discrete Mathematics 05C12 (Primary) 05C15, 05C57 (Secondary) G.2.2; G.2.3 |
| url | https://arxiv.org/abs/2408.09997 |