The generalized Turán number of spanning linear forests

DOI10.1007/S00373-021-02403-9MaRDI QIDQ2115153zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 15 March 2022

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

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

zbMATH Keywords

linear forestshifting methodgeneralized Turán number

Mathematics Subject Classification ID

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

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}^{\ast }$ 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}^{\ast },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.

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

Cites work

• scientific article; zbMATH DE number 3685495 (Why is no real title available?)
• scientific article; zbMATH DE number 3050594 (Why is no real title available?)
• A generalized Turán problem and its applications
• Counting copies of a fixed subgraph in \(F\)-free graphs
• 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
• Many \(T\) copies in \(H\)-free graphs
• On graphs with randomly deleted edges
• On maximal paths and circuits of graphs
• Planar Turán numbers of short paths
• Some sharp results on the generalized Turán numbers
• The formula for Turán number of spanning linear forests
• The history of degenerate (bipartite) extremal graph problems
• The maximum number of cliques in graphs without long cycles
• The maximum number of triangles in \(C_{2k+1}\)-free graphs
• The shifting method and generalized Turán number of matchings

Cited in

(18)

• 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
• Generalized Turán number for linear forests
• The formula for Turán number of spanning linear forests
• The shifting method and generalized Turán number of matchings
• Generalized Turán problems for complete bipartite graphs
• The Turán number of Berge hypergraphs with stable properties
• Determinantal generating functions of colored spanning forests
• Stability of generalized Tur\'an number for linear forests
• Saturation numbers for linear forests P₅ tP₂
• The maximum number of complete multipartite subgraphs in graphs with given circumference or matching number
• On the Turán numbers of linear forests in bipartite graphs
• Turán numbers of general star forests in hypergraphs
• The bipartite Turán number and spectral extremum for linear forests
• The Turán number for spanning linear forests
• The generalized Turán number of linear forests

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)