Turán number of the odd-ballooning of complete bipartite graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910443519344640 |
|---|---|
| author | Peng, Xing Xia, Mengjie |
| author_facet | Peng, Xing Xia, Mengjie |
| contents | Given a graph $L$, the Turán number $\textrm{ex}(n,L)$ is the maximum possible number of edges in an $n$-vertex $L$-free graph. The study of Turán number of graphs is a central topic in extremal graph theory. Although the celebrated Erdős-Stone-Simonovits theorem gives the asymptotic value of $\textrm{ex}(n,L)$ for nonbipartite $L$, it is challenging in general to determine the exact value of $\textrm{ex}(n,L)$ for $χ(L) \geq 3$. The odd-ballooning of $H$ is a graph such that each edge of $H$ is replaced by an odd cycle and all new vertices of odd cycles are distinct. Here the length of odd cycles is not necessarily equal. The exact value of Turán number of the odd-ballooning of $H$ is previously known for $H$ being a cycle, a path, a tree with assumptions, and $K_{2,3}$. In this paper, we manage to obtain the exact value of Turán number of the odd-ballooning of $K_{s,t}$ with $2\leq s \leq t$, where $(s,t) \not \in \{(2,2),(2,3)\} $ and each odd cycle has length at least five. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_04984 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Turán number of the odd-ballooning of complete bipartite graphs Peng, Xing Xia, Mengjie Combinatorics 05C35, 05C38 Given a graph $L$, the Turán number $\textrm{ex}(n,L)$ is the maximum possible number of edges in an $n$-vertex $L$-free graph. The study of Turán number of graphs is a central topic in extremal graph theory. Although the celebrated Erdős-Stone-Simonovits theorem gives the asymptotic value of $\textrm{ex}(n,L)$ for nonbipartite $L$, it is challenging in general to determine the exact value of $\textrm{ex}(n,L)$ for $χ(L) \geq 3$. The odd-ballooning of $H$ is a graph such that each edge of $H$ is replaced by an odd cycle and all new vertices of odd cycles are distinct. Here the length of odd cycles is not necessarily equal. The exact value of Turán number of the odd-ballooning of $H$ is previously known for $H$ being a cycle, a path, a tree with assumptions, and $K_{2,3}$. In this paper, we manage to obtain the exact value of Turán number of the odd-ballooning of $K_{s,t}$ with $2\leq s \leq t$, where $(s,t) \not \in \{(2,2),(2,3)\} $ and each odd cycle has length at least five. |
| title | Turán number of the odd-ballooning of complete bipartite graphs |
| topic | Combinatorics 05C35, 05C38 |
| url | https://arxiv.org/abs/2307.04984 |