生成线性森林的极值问题

doi:10.15960/j.cnki.issn.1007-6093.2025.04.008

运筹学学报（中英文） ›› 2025, Vol. 29 ›› Issue (4): 94-102.doi: 10.15960/j.cnki.issn.1007-6093.2025.04.008

• • 上一篇

生成线性森林的极值问题

季雪†, 康丽英, 薛益赛

上海大学数学系, 上海 200444

收稿日期:2022-03-16 发布日期:2025-12-11
通讯作者: 季雪 E-mail:jixuexingyun@163.com
基金资助:
国家自然科学基金(Nos.11871329,11971298)

The extremal problem of spanning linear forests

JI Xue†, KANG Liying, XUE Yisai

Department of Mathematics, Shanghai University, Shanghai 200444, China

Received:2022-03-16 Published:2025-12-11

摘要/Abstract

摘要： 设$\mathcal{F}$ 是一个图族, 如果$G$ 不包含$\mathcal{F}$ 中的任意一个图作为子图, 则称$G$ 是禁用图族$\mathcal{F}$ 的。禁用图族$\mathcal{F}$ 的$n$ 阶图所能达到的最大边数称为$\mathcal{F}$ 的Turán 数, 记作$ex(n,\mathcal{F})$。线性森林是指连通分支都是路或孤立点的图。设$\mathcal{L}_{n,k}'$ 是一个除图$P_{k+1}\cup(n-k-1)K_1$ 外, 包含其他所有边数为$k$ 的$n$ 阶线性森林组成的图族。本文给出了$\mathcal{L}_{n,k}'$ 的Turán 数和对应的极值图。进一步我们给出了禁用$\mathcal{L}_{n,k}'$ 的$n$ 阶图的谱半径的最大值和对应的极值图。

关键词: 线性森林, Turán 数, 谱半径, 极值图

Abstract: Let $\mathcal{F}$ be a family of graphs. If $G$ does not contain every graph in $\mathcal{F}$ as a subgraph, then $G$ is said to be $\mathcal{F}$-free. The Turán number $ex(n,\mathcal{F})$ is defined to be the maximum number of edges in a graph on $n$ vertices that is $\mathcal{F}$-free. A linear forest is a graph whose connected components are all paths or isolated vertices. Let $\mathcal{L}_{n,k}'$ be the family of all linear forests of order $n$ with $k$ edges except $P_{k+1}\cup(n-k-1)K_1$. In this paper, we give Turán number of $\mathcal{L}_{n,k}'$ and corresponding extremal graphs. Furthermore, we give the maximum spectral radius of graphs of order $n$ that are $\mathcal{L}_{n,k}'$-free and the corresponding extremal graphs.

Key words: linear forest, Turán number, spectral radius, extremal graphs

中图分类号:

O157.5

季雪, 康丽英, 薛益赛. 生成线性森林的极值问题[J]. 运筹学学报（中英文）, 2025, 29(4): 94-102.

JI Xue, KANG Liying, XUE Yisai. The extremal problem of spanning linear forests[J]. Operations Research Transactions, 2025, 29(4): 94-102.

参考文献

[1] Turán P. On an external problem in graph theory [J]. Matematikaiés Lapok, 1941, 48: 436-452.
[2] Erdős P, Gallai T. On maximal paths and circuits of graphs [J]. Acta Mathematica Academiae Scientiarum Hungarica, 1959, 10: 337-356.
[3] Bushaw N, Kettle N. Turán numbers of multiple paths and equibipartite forests [J]. Combinatorics, Probability and Computing, 2011, 20(6): 837-853.
[4] Yuan L T, Zhang X D. The Turán number of disjoint copies of paths [J]. Discrete Mathematics, 2017, 340: 132-139.
[5] Lidicky B, Liu H, Palmer C. On the Turán number of forests [J]. The Electronic Journal of Combinatorics, 2012, 20(2): 713-718.
[6] Ning B, Wang J. The formula for Turán number of spanning linear forests [J]. Discrete Mathematics, 2020, 343: 111924.
[7] Brualdi R A, Hoffman A J. On the spectral radius of (0,1)-matrices [J]. Linear Algebra and its Applications, 1985, 65: 133-146.
[8] Nikiforov V. Bounds on graph eigenvalues II [J]. Linear Algebra and Its Applications, 2006, 427: 183-189.
[9] Nikiforov V. Some New Results in Extremal Graph Theory [M]. Cambridge: Cambridge University Press, 2011.
[10] Nikiforov V. The spectral radius of graphs without paths and cycles of specified length [J]. Linear Algebra and Its Applications, 2010, 432(9): 2243-2256.
[11] Chen M Z, Zhang X D. Spectral extremal results with forbidding linear forests [J]. Graphs and Combinatorics, 2019, 35: 335-351.
[12] Dirac G A. Some theorems on abstract graphs [J]. Proceedings of the London Mathematical Society, 1952, 2: 69-81.
[13] Chen M Z, Zhang X D. Erdős-Gallai stability theorem for linear forests [J]. Discrete Mathematics, 2019, 342: 904-916.
[14] Yuan H, Shu J L, Fang K. A sharp upper bound of the spectral radius of graphs [J]. Journal of Combinatorial Theory, 2001, 81(2): 177-183.
[15] Nikiforov V. Some inequalities for the largest eigenvalue of a graph [J]. Combinatorics, Probability and Computing, 2002, 11(2): 179-189.

生成线性森林的极值问题

The extremal problem of spanning linear forests

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 14

编辑推荐

Metrics

本文评价

[1]	吴志伟, 康丽英. 可消去超图p-谱半径的极值问题[J]. 运筹学学报（中英文）, 2025, 29(2): 194-200.
[2]	杨禹, 朱忠熏, 周鋆鹏. 给定悬挂点数的具有最大无符号拉普拉斯谱半径的k一致超图[J]. 运筹学学报（中英文）, 2025, 29(1): 185-197.
[3]	余桂东, 刘珍珍, 王礼想, 李青. 可迹图的一些新充分条件[J]. 运筹学学报（中英文）, 2024, 28(1): 131-140.
[4]	何常香, 王文燕, 刘乐乐. 关于赋权非正则图的A_α特征值和特征向量[J]. 运筹学学报（中英文）, 2024, 28(1): 121-130.
[5]	刘乐乐, 宁博. 谱图理论中的未解决问题[J]. 运筹学学报, 2023, 27(4): 33-60.
[6]	贾会才, 宋宏业. 基于Wiener指数和Harary指数的泛圈图的充分条件[J]. 运筹学学报, 2023, 27(3): 169-177.
[7]	陈洪玲, 王慧娟, 孙凤艳, 薛娟, 高红伟. 最大度大于等于7的平面图的线性荫度[J]. 运筹学学报, 2020, 24(3): 154-160.
[8]	陈媛媛, 王国平. 三圈图的无符号拉普拉斯谱半径[J]. 运筹学学报, 2019, 23(1): 81-89.
[9]	余桂东, 周甫, 刘琦. 可迹图的谱充分条件[J]. 运筹学学报, 2017, 21(1): 118-124.
[10]	李浙宁，凌晨，王宜举，杨庆之. 张量分析和多项式优化的若干进展[J]. 运筹学学报, 2014, 18(1): 134-148.
[11]	陈艳, 袁西英, 韩苗苗. 关于三圈图的拉普拉斯谱半径的一些结果[J]. 运筹学学报, 2011, 15(4): 1-8.
[12]	吴廷增, 扈生彪. m重似星树的谱半径[J]. 运筹学学报, 2011, 15(3): 45-50.
[13]	陈琳黄琼湘. 给定顶点数和边数的连通图的Q-谱半径的界[J]. 运筹学学报, 2011, 15(3): 19-28.
[14]	陈琳, 黄琼湘. 给定顶点数和边数的连通图的Q-谱半径[J]. 运筹学学报, 2011, (3): 19-28.