Vertex-Based Localization of Turán's Theorem
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912372391673856 |
|---|---|
| author | Adak, Rajat Chandran, L. Sunil |
| author_facet | Adak, Rajat Chandran, L. Sunil |
| contents | Let $G$ be a simple graph with $n$ vertices and $m$ edges. According to Turán's theorem, if $G$ is $K_{r+1}$-free, then $m \leq |E(T(n, r))|,$ where $T(n, r)$ denotes the Turán graph on $n$ vertices with a maximum clique of order $r$. A limitation of this statement is that it does not give an expression in terms of $n$ and $r$. A widely used version of Turán's theorem states that for an $n$-vertex $K_{r+1}$-free graph, $m \leq \left\lfloor \frac{n^2(r-1)}{2r} \right\rfloor.$ Though this bound is often more convenient, it is not the same as the original statement. In particular, the class of extremal graphs for this bound, say $\mathcal{S}$, is a proper subset of the set of Turán graphs. In this paper, we generalize this result as follows: For each $v \in V(G)$, let $c(v)$ be the order of the largest clique that contains $v$. We show that \[ m \leq \left\lfloor\frac{n}{2}\sum_{v\in V(G)}\frac{c(v)-1}{c(v)}\right\rfloor\] Furthermore, we characterize the class of extremal graphs that attain equality in this bound. Interestingly, this class contains two extra non-Turán graphs other than the graphs in $\mathcal{S}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_02806 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Vertex-Based Localization of Turán's Theorem Adak, Rajat Chandran, L. Sunil Combinatorics Discrete Mathematics Let $G$ be a simple graph with $n$ vertices and $m$ edges. According to Turán's theorem, if $G$ is $K_{r+1}$-free, then $m \leq |E(T(n, r))|,$ where $T(n, r)$ denotes the Turán graph on $n$ vertices with a maximum clique of order $r$. A limitation of this statement is that it does not give an expression in terms of $n$ and $r$. A widely used version of Turán's theorem states that for an $n$-vertex $K_{r+1}$-free graph, $m \leq \left\lfloor \frac{n^2(r-1)}{2r} \right\rfloor.$ Though this bound is often more convenient, it is not the same as the original statement. In particular, the class of extremal graphs for this bound, say $\mathcal{S}$, is a proper subset of the set of Turán graphs. In this paper, we generalize this result as follows: For each $v \in V(G)$, let $c(v)$ be the order of the largest clique that contains $v$. We show that \[ m \leq \left\lfloor\frac{n}{2}\sum_{v\in V(G)}\frac{c(v)-1}{c(v)}\right\rfloor\] Furthermore, we characterize the class of extremal graphs that attain equality in this bound. Interestingly, this class contains two extra non-Turán graphs other than the graphs in $\mathcal{S}$. |
| title | Vertex-Based Localization of Turán's Theorem |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2504.02806 |