生成线性森林的极值问题

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

生成线性森林的极值问题

季雪¹^,*(), 康丽英¹, 薛益赛¹

1. 上海大学数学系, 上海 200444

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

The extremal problem of spanning linear forests

Xue JI¹^,*(), Liying KANG¹, Yisai XUE¹

1. Department of Mathematics, Shanghai University, Shanghai 200444, China

Received:2022-03-16 Online:2025-12-15 Published:2025-12-11
Contact: Xue JI E-mail:jixuexingyun@163.com

摘要/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.

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

图/表 2

参考文献 15

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. doi: 10.1007/BF02024498
3	Bushaw N , Kettle N .Turán numbers of multiple paths and equibipartite forests[J].Combinatorics, Probability and Computing,2011,20(6):837-853. doi: 10.1017/S0963548311000460
4	Yuan L T , Zhang X D .The Turán number of disjoint copies of paths[J].Discrete Mathematics,2017,340,132-139. doi: 10.1016/j.disc.2016.08.004
5	Lidický 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. doi: 10.1016/0024-3795(85)90092-8
8	Nikiforov V .Bounds on graph eigenvalues Ⅱ[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. doi: 10.1016/j.laa.2009.05.023
11	Chen M Z , Zhang X D .Spectral extremal results with forbidding linear forests[J].Graphs and Combinatorics,2019,35,335-351. doi: 10.1007/s00373-018-1996-3
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. doi: 10.1016/j.disc.2018.11.021
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. doi: 10.1006/jctb.2000.1997
15	Nikiforov V .Some inequalities for the largest eigenvalue of a graph[J].Combinatorics, Probability and Computing,2002,11(2):179-189. doi: 10.1017/S0963548301004928

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

生成线性森林的极值问题

The extremal problem of spanning linear forests

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 2

参考文献 15

相关文章 15

编辑推荐

Metrics

本文评价