论文标题
跨越线性森林数量
The generalized Turán number of spanning linear forests
论文作者
论文摘要
令$ \ mathcal {f} $为图形家庭。图$ g $称为\ textIt {$ \ mathcal {f} $ - free}如果对于任何$ f \ in \ mathcal {f} $中的任何$ f \，则没有$ g $ isomorphic的子图至$ f $。给定图形$ t $和一个图$ \ MATHCAL {F} $，$ \ MATHCAL {F} $的概括是$ \ Mathcal {f} $中$ t $的最大副本数量 - $ n $ vertices上的免费图形，在$ n $ vertices上，$ n $ vertices，$ n $ vertices，由$ ex（n，t，t，t，t，mathcal c}表示）。线性森林是一个图形，其连接的组件都是所有路径或孤立的顶点。令$ \ MATHCAL {l} _ {n，k} $成为所有线性$ n $带有$ k $ edges和$ k^*_ {s，t} $的家族，从$ k_ {s，t} $获得尺寸$ s $的零件$ s $与同一尺寸的列表相同的零件。在本文中，我们确定$ ex（n，k_s，\ Mathcal {l} _ {n，k}）$和$ ex（n，k^*_ {s，t}，\ Mathcal {l} _ {n，k}）$的确切值。另外，当\ textIt {“主机图”}是两部分时，我们研究了此问题的情况。用$ ex_ {bip}表示（n，t，\ mathcal {f}）$ $ \ mathcal {f} $中的$ t $的最大副本数量 - 免费的双分式图形，每个部分的大小$ n $。我们确定$ ex_ {bip}（n，k_ {s，t}，\ mathcal {l} _ {n，k}）$的确切值。我们的证明主要基于转移方法。
Let $\mathcal{F}$ be a family of graphs. A graph $G$ is called \textit{$\mathcal{F}$-free} if for any $F\in \mathcal{F}$, there is no subgraph of $G$ isomorphic to $F$. Given a graph $T$ and a family of graphs $\mathcal{F}$, the generalized Turán number of $\mathcal{F}$ is the maximum number of copies of $T$ in an $\mathcal{F}$-free graph on $n$ vertices, denoted by $ex(n,T,\mathcal{F})$. 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 \textit{"host graph"} is bipartite. Denote by $ex_{bip}(n,T,\mathcal{F})$ the maximum possible number of copies of $T$ in an $\mathcal{F}$-free bipartite graph with each part of size $n$. We determine the exact value of $ex_{bip}(n,K_{s,t},\mathcal{L}_{n,k})$. Our proof is mainly based on the shifting method.
