The generalized Turán number of spanning linear forests

DOI10.1007/S00373-021-02403-9zbMATH Open1485.05029arXiv2009.00181OpenAlexW4210342670MaRDI QIDQ2115153FDOQ2115153

Yanyan Li

Publication date: 15 March 2022

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: Let $mathcalF$ be a family of graphs. A graph $G$ is called extit{$mathcalF$-free} if for any $FinmathcalF$, there is no subgraph of $G$ isomorphic to $F$. Given a graph $T$ and a family of graphs $mathcalF$, the generalized Tur'{a}n number of $mathcalF$ is the maximum number of copies of $T$ in an $mathcalF$-free graph on $n$ vertices, denoted by $ex(n,T,mathcalF)$. 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 and $K_{s,t}^{*}$ a graph obtained from $K_{s,t}$ by substituting the part of size $s$ with a clique of the same size. In this paper, we determine the exact values of $ex(n,K_s,mathcal{L}_{n,k})$ and $ex(n,K_{s,t}^{*},mathcal{L}_{n,k})$. Also, we study the case of this problem when the extit{"host graph"} is bipartite. Denote by $e{x}_{bip}(n,T,mathcalF)$ the maximum possible number of copies of $T$ in an $mathcalF$-free bipartite graph with each part of size $n$. We determine the exact value of $e{x}_{bip}(n,K_{s,t},mathcal{L}_{n,k})$. Our proof is mainly based on the shifting method.

Full work available at URL: https://arxiv.org/abs/2009.00181

Recommendations

• The maximum number of stars in a graph without linear forest
• Generalized Turán number of even linear forests
• Generalized Turán number for linear forests
• The shifting method and generalized Turán number of matchings
• Generalized Turán problems for complete bipartite graphs
• Some Stability and Exact Results in Generalized Turán Problems
• Forbidding multiple copies of forestable graphs
• The Turán number for spanning linear forests
• The bipartite Turán number and spectral extremum for linear forests
• The Turán number of star forests

zbMATH Keywords

linear forestshifting methodgeneralized Turán number

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35)

Cites Work

• On graphs with randomly deleted edges
• On maximal paths and circuits of graphs
• The History of Degenerate (Bipartite) Extremal Graph Problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• The maximum number of triangles in \(C_{2k+1}\)-free graphs
• Many \(T\) copies in \(H\)-free graphs
• The maximum number of cliques in graphs without long cycles
• Extensions of the Erdős–Gallai theorem and Luo’s theorem
• Generalized Turán problems for disjoint copies of graphs
• Generalized Turán problems for even cycles
• Some sharp results on the generalized Turán numbers
• A Generalized Turán Problem and its Applications
• Counting copies of a fixed subgraph in \(F\)-free graphs
• The formula for Turán number of spanning linear forests
• The shifting method and generalized Turán number of matchings
• Planar Turán numbers of short paths

Cited In (10)

• Spectral radius and rainbow Hamilton paths of a graph
• The maximum spectral radius of graphs without spanning linear forests
• Generalized Turán number of even linear forests
• Further results on the generalized Turán number of spanning linear forests
• The formula for Turán number of spanning linear forests
• The Turán number of Berge hypergraphs with stable properties
• Determinantal generating functions of colored spanning forests
• Saturation numbers for linear forests \(P_5\cup tP_2\)
• The maximum number of complete multipartite subgraphs in graphs with given circumference or matching number
• Turán numbers of general star forests in hypergraphs

This page was built for publication: The generalized Turán number of spanning linear forests

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2115153)