A Weighted Generalization of Turán's Theorem

NEW

Problem: Reconstructed statement: for integers $m\ge1$ and $n\ge m+1$, characterize all nonnegative integer edge-weighted graphs $G$ on $n$ vertices such that every induced $(m+1)$-vertex subgraph has total weight at most

and $G$ has maximum possible total weight. Bondy–Tuza’s weighted Turán theorem gives this maximum as the ordinary Turán number $t_m(n)$.

Result: Let $t_m(n)$ be the number of edges of the balanced complete $m$-partite Turán graph, i.e. if $n=qm+r$, $0\le r<m$, then

For $n>m+1$, put

The $(m,n)$-extremal graphs are exactly the following recursively defined class.

Base case $n=m+1$: all nonnegative integer weightings of $K_{m+1}$ of total weight

Recursive step $n>m+1$: an admissible weighted graph $G$ on $n$ vertices is $(m,n)$-extremal iff there exists a vertex $v$ such that

and $G-v$ is $(m,n-1)$-extremal.

Proof: If $G$ is extremal, then by Bondy–Tuza,

For every vertex $v$, the deletion $G-v$ is still admissible, so

hence

But the average weighted degree of the Turán graph is $2t_m(n)/n<\delta_m(n)+1$, so not every vertex of $G$ can have degree at least $\delta_m(n)+1$. Thus some $v$ has $d_G(v)=\delta_m(n)$, and then

so $G-v$ is extremal.

Conversely, if $G$ is admissible, $G-v$ is $(m,n-1)$-extremal, and $d_G(v)=\delta_m(n)$, then

so $G$ is $(m,n)$-extremal.

Thus the recursive description is necessary and sufficient for all $m,n$. It includes the small non-Turán extremals, e.g. for $m=2,n=4$, the double matching as well as $C_4$.

Citation: Bondy–Tuza prove the weighted Turán maximum $t_m(n)$: J. A. Bondy and Zs. Tuza, “A weighted generalization of Turán’s theorem,” Journal of Graph Theory 25 (1997), 267–275.