# The maximum number of triangles in graphs without large linear forests

Research paper by **Xiuzhuan Duan, Jian Wang, Weihua Yang**

Indexed on: **21 Dec '18**Published on: **21 Dec '18**Published in: **arXiv - Mathematics - Combinatorics**

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join for free

#### Abstract

Let $G$ be a graph on $n$ vertices. A linear forest is a graph consisting of
vertex-disjoint paths and isolated vertices. A maximum linear forest of $G$ is
a subgraph of $G$ with maximum number of edges, which is a linear forest. We
denote by $l(G)$ this maximum number. Let $t=\left\lfloor (k-1)/2\right
\rfloor$. Recently, Ning and Wang \cite{boning} proved that if $l(G)=k-1$, then
for any $k<n$ \[ e(G) \leq \max \left\{\binom{k}{2},\binom{t}{2}+t (n - t)+ c
\right\}, \] where $c=0$ if $k$ is odd and $c=1$ otherwise, and the inequality
is tight. In this paper, we prove that if $l(G)=k-1$ and $\delta(G)=\delta$
($\delta<\lfloor k/2 \rfloor$), then for any $k<n$ \[ e(G) \leq \max
\left\{\binom{k-\delta}{2}+\delta(n-k+\delta),\binom{t}{2}+t\left(n-t\right)+c
\right\}. \] When $\delta=0$, it reduces to Ning and Wang's result. Moreover,
let $r_3(G)$ be the number of triangles in $G$. We prove that if $l(G)=k-1$ and
$\delta(G)= \delta$, then for any $k<n$ \[ r_3(G)\leq \max
\left\{\binom{k-\delta}{3}+\binom{\delta}{2}(n-k+\delta),\binom{t}{3}+\binom{t}{2}\left(n-t\right)+d
\right\}. \] where $d=0$ if $k$ is odd and $d=t$ otherwise.