论文

生成线性森林的极值问题

  • 季雪 ,
  • 康丽英 ,
  • 薛益赛
展开
  • 1. 上海大学数学系, 上海 200444
季雪   E-mail: jixuexingyun@163.com

收稿日期: 2022-03-16

  网络出版日期: 2025-12-11

基金资助

国家自然科学基金(11871329);国家自然科学基金(11971298)

版权

运筹学学报编辑部, 2025, 版权所有,未经授权,不得转载。

The extremal problem of spanning linear forests

  • Xue JI ,
  • Liying KANG ,
  • Yisai XUE
Expand
  • 1. Department of Mathematics, Shanghai University, Shanghai 200444, China

Received date: 2022-03-16

  Online published: 2025-12-11

Copyright

, 2025, All rights reserved. Unauthorized reproduction is prohibited.

摘要

$\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$阶图的谱半径的最大值和对应的极值图。

本文引用格式

季雪 , 康丽英 , 薛益赛 . 生成线性森林的极值问题[J]. 运筹学学报, 2025 , 29(4) : 94 -102 . DOI: 10.15960/j.cnki.issn.1007-6093.2025.04.008

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.

参考文献

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 Ⅱ[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.
文章导航

/