Sparse graphs with local covering conditions on edges
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912031814189056 |
|---|---|
| author | Chakraborti, Debsoumya Madani, Amirali Maheshwari, Anil Miraftab, Babak |
| author_facet | Chakraborti, Debsoumya Madani, Amirali Maheshwari, Anil Miraftab, Babak |
| contents | In 1988, Erdős suggested the question of minimizing the number of edges in a connected $n$-vertex graph where every edge is contained in a triangle. Shortly after, Catlin, Grossman, Hobbs, and Lai resolved this in a stronger form. In this paper, we study a natural generalization of the question of Erdős in which we replace `triangle' with `clique of order $k$' for ${k\ge 3}$. We completely resolve this generalized question with the characterization of all extremal graphs. Motivated by applications in data science, we also study another generalization of the question of Erdős where every edge is required to be in at least $\ell$ triangles for $\ell\ge 2$ instead of only one triangle. We completely resolve this problem for $\ell = 2$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_11216 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Sparse graphs with local covering conditions on edges Chakraborti, Debsoumya Madani, Amirali Maheshwari, Anil Miraftab, Babak Combinatorics In 1988, Erdős suggested the question of minimizing the number of edges in a connected $n$-vertex graph where every edge is contained in a triangle. Shortly after, Catlin, Grossman, Hobbs, and Lai resolved this in a stronger form. In this paper, we study a natural generalization of the question of Erdős in which we replace `triangle' with `clique of order $k$' for ${k\ge 3}$. We completely resolve this generalized question with the characterization of all extremal graphs. Motivated by applications in data science, we also study another generalization of the question of Erdős where every edge is required to be in at least $\ell$ triangles for $\ell\ge 2$ instead of only one triangle. We completely resolve this problem for $\ell = 2$. |
| title | Sparse graphs with local covering conditions on edges |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2409.11216 |