Extremal graph theory studies the maximum or minimum number of subgraphs isomorphic to a prescribed graph under given constraints. Localization has recently emerged as a framework that refines such problems by assigning extremal quantities locally (to vertices or edges) and then aggregating them. This perspective not only recovers classical results but also leads to sharper bounds. A classical result states that a connected planar graph with a finite girth g satisfies \( m \le \frac{g}{g-2}(n-2) \) Wood [19] derived upper bounds on the number of \(K_t\) -cliques in graphs of bounded maximum degree, expressed in terms of both the number of vertices and the number of edges: \(\begin{aligned} ex(n,K_t,K_{1,d+1}) \le \frac{n}{d+1}\left( {\begin{array}{c}d+1\\ t\end{array}}\right) \\ mex(m,K_t,K_{1,d+1}) \le \frac{m}{\left( {\begin{array}{c}d+1\\ 2\end{array}}\right) }\left( {\begin{array}{c}d+1\\ t\end{array}}\right) \end{aligned}\) More recently, Chakraborty and Chen [9] established a similar upper bound for graphs with bounded path length: \(\begin{aligned} mex(m,K_t,P_{r+1}) \le \frac{m}{\left( {\begin{array}{c}r\\ 2\end{array}}\right) }\left( {\begin{array}{c}r\\ t\end{array}}\right) \end{aligned}\) In this paper, we employ the localization framework to improve these bounds and provide structural characterizations of the extremal graphs attaining them.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Localization: A Framework to Generalize Extremal Graph Problems

  • Rajat Adak,
  • L. Sunil Chandran

摘要

Extremal graph theory studies the maximum or minimum number of subgraphs isomorphic to a prescribed graph under given constraints. Localization has recently emerged as a framework that refines such problems by assigning extremal quantities locally (to vertices or edges) and then aggregating them. This perspective not only recovers classical results but also leads to sharper bounds. A classical result states that a connected planar graph with a finite girth g satisfies \( m \le \frac{g}{g-2}(n-2) \) Wood [19] derived upper bounds on the number of \(K_t\) -cliques in graphs of bounded maximum degree, expressed in terms of both the number of vertices and the number of edges: \(\begin{aligned} ex(n,K_t,K_{1,d+1}) \le \frac{n}{d+1}\left( {\begin{array}{c}d+1\\ t\end{array}}\right) \\ mex(m,K_t,K_{1,d+1}) \le \frac{m}{\left( {\begin{array}{c}d+1\\ 2\end{array}}\right) }\left( {\begin{array}{c}d+1\\ t\end{array}}\right) \end{aligned}\) More recently, Chakraborty and Chen [9] established a similar upper bound for graphs with bounded path length: \(\begin{aligned} mex(m,K_t,P_{r+1}) \le \frac{m}{\left( {\begin{array}{c}r\\ 2\end{array}}\right) }\left( {\begin{array}{c}r\\ t\end{array}}\right) \end{aligned}\) In this paper, we employ the localization framework to improve these bounds and provide structural characterizations of the extremal graphs attaining them.