Structure of (bull, diamond)-free graphs and its applications
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2021
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913470068293632 |
|---|---|
| author | Mishra, Suchismita |
| author_facet | Mishra, Suchismita |
| contents | This paper discusses the complete structure of the (bull, diamond)-free graphs. As an application of that, we give the characterization of the partitionable (bull, diamond)-free graphs. Moreover, we show that such a partition for a partitionable (bull, diamond)-free graph can be found in polynomial time. Additionally, we show that the cop number of a (bull, diamond)-free graph containing a triangle is at most two less than its diameter. Furthermore, the cop number of a connected ($P_n$, bull, diamond)-free graph with a triangle, is at most $n-3$, for any natural number $n>3$. We also discuss a couple of applications of the structural theorem of the (bull, diamond)-free graphs in the conclusions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2107_03750 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Structure of (bull, diamond)-free graphs and its applications Mishra, Suchismita Combinatorics This paper discusses the complete structure of the (bull, diamond)-free graphs. As an application of that, we give the characterization of the partitionable (bull, diamond)-free graphs. Moreover, we show that such a partition for a partitionable (bull, diamond)-free graph can be found in polynomial time. Additionally, we show that the cop number of a (bull, diamond)-free graph containing a triangle is at most two less than its diameter. Furthermore, the cop number of a connected ($P_n$, bull, diamond)-free graph with a triangle, is at most $n-3$, for any natural number $n>3$. We also discuss a couple of applications of the structural theorem of the (bull, diamond)-free graphs in the conclusions. |
| title | Structure of (bull, diamond)-free graphs and its applications |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2107.03750 |