中文

Operations Research Transactions >

2025 , Vol. 29 >Issue 4: 94 - 102

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2025.04.008

Research Article

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.
Fold

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

Cite this article

Xue JI , Liying KANG , Yisai XUE . The extremal problem of spanning linear forests[J]. Operations Research Transactions, 2025 , 29(4) : 94 -102 . DOI: 10.15960/j.cnki.issn.1007-6093.2025.04.008

References

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.
Options
Outlines

/

〈 〉