{ "id": "2504.02806", "version": "v3", "published": "2025-04-03T17:51:50.000Z", "updated": "2025-05-13T10:27:55.000Z", "title": "Vertex-Based Localization of Turán's Theorem", "authors": [ "Rajat Adak", "L. Sunil Chandran" ], "categories": [ "math.CO", "cs.DM" ], "abstract": "Let $G$ be a simple graph with $n$ vertices and $m$ edges. According to Tur\\'{a}n's theorem, if $G$ is $K_{r+1}$-free, then $m \\leq |E(T(n, r))|,$ where $T(n, r)$ denotes the Tur\\'{a}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\\'{a}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\\'{a}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\\'{a}n graphs other than the graphs in $\\mathcal{S}$.", "revisions": [ { "version": "v3", "updated": "2025-05-13T10:27:55.000Z" } ], "analyses": { "keywords": [ "turáns theorem", "vertex-based localization", "extremal graphs", "free graph", "original statement" ], "note": { "typesetting": "TeX", "pages": 0, "language": "en", "license": "arXiv", "status": "editable" } } }