2504.02806

#1 Vertex-Based Localization of Turán's Theorem [PDF] [Copy] [Kimi] [REL]

Author: Rajat Adak

For a simple graph $G$, let $n$ and $m$ denote the number of vertices and edges in $G$, respectively. Turán's theorem states that in a simple $K_{r+1}$ free graph, $m \leq \frac{n^2(r-1)}{2r}$. 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 \frac{n}{2}\sum_{v\in V(G)}\frac{c(v)-1}{c(v)}$$ Furthermore, we characterize the class of extremal graphs that attain equality in this bound.

Subjects: Combinatorics , Discrete Mathematics

Publish: 2025-04-03 17:51:50 UTC

---