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

The Turán number of \(P_9 \cup P_7\)

  • Xiaona Fang,
  • Lihua You

摘要

The Turán number of a graph F is the maximum number of edges in any graph on n vertices containing no F as a subgraph. Let \(P_{\ell }\) P denote the path on \(\ell \) vertices. A linear forest, denoted by \(\mathop {\cup }\nolimits _{i=1}^{k} P_{\ell _i}\) i = 1 k P i , is a forest whose connected components are paths. Lidický et al. (Electron J Combin 20(2):62, 2013) considered the Turán number of linear forests for sufficiently large n. Yuan and Zhang (J Graph Theory 98(3):499–524, 2021) determined the Turán numbers of the linear forests containing at most one odd path for all n and proposed a conjecture, which is confirmed to be true for \(P_3\cup P_{2\ell +1}\) P 3 P 2 + 1 , \(2P_5\) 2 P 5 , \(3P_5\) 3 P 5 , \(2P_7\) 2 P 7 , \(2P_9\) 2 P 9 , \(3P_7\) 3 P 7 and \(2P_3\cup P_{2\ell +1}\) 2 P 3 P 2 + 1 . Motivated by these results, we determine the Turán numbers of \(P_9 \cup P_7\) P 9 P 7 for all \(n\ge 16\) n 16 and characterize all extremal graphs, which partially confirms the conjecture proposed by Yuan and Zhang.