The generalized Turán number of $2 S_\ell$

1.   Introduction

All graphs in this paper are finite, simple and undirected. Terms and notations not defined here are from ^[1]. Let $S_\ell$ denote the star on $\ell+1$ vertices. Let $G$ be a graph with vertex set $V(G)$ and edge set $E(G)$. If $v\in V(G)$, the degree of $v$ is the number of edges incident to $v$, is denoted by $d_G(v)$. Let $N_G(v)$ be the set of neighbors of $v$ in $G$, and $N_G[v] = N_G(v)\cup\{v\}$. Clearly, $d_G(v) = |N_G(v)|$. Let $\Delta (G)$ denote the maximum degree of $G$. The vertex with degree $\ell$ in $S_\ell$ is called the center of $S_\ell$. For two disjoint graphs $G$ and $H$, $G\cup H$ denotes the disjoint union of $G$ and $H$, $pG$ denotes the disjoint union of $p$ copies of $G$ and $G\vee H$ denotes the graph obtained from $G\cup H$ by adding all edges between $V(G)$ and $V(H)$. For $S\subseteq V(G)$, we use $G-S$ to denote the subgraph obtained from $G$ by deleting the vertices in $S$ together with their incident edges, and the subgraph of $G$ induced by $S$ is denoted by $G[S]$.

Let ${\mathcal{N}}_s(G)$ denote the number of copies of $K_s$ in $G$. For $s\ge 2$ and a given graph $H$, the generalized Turán number $ex{(n, K_s, H)}$ is defined to be the maximum number of copies of $K_s$ in any $H$-free graph on $n$ vertices. An $H$-free graph on $n$ vertices which contains the maximum number of copies of $K_s$, is called an extremal graph for $H$. Moreover, we denote $EX(n, K_s, H)$ to be the family of all extremal graphs on $n$ vertices for $H$. If $s = 2$, we simply write $ex{(n, H)}$ for $ex{(n, K_s, H)}$, which is the classical Turán number. Turán determined $ex(n, K_{r+1})$ and showed that $T_r(n)$ is the unique extremal graph for $K_{r+1}$, where $T_r(n)$ is the $r$-partite Turán graph on $n$ vertices. It was shown by Simonovits ^[12] that if $n$ is sufficiently large, then $K_{p-1}\vee T_r (n-p+1)$ is the unique extremal graph for $pK_{r+1}$. For any connected graph $G$ on $n$ vertices, Gorgol ^[7] gave a lower bound for $ex(m, pG)$.

Theorem 1.1. ^[7] Let $G$ be an arbitrary connected graph on $n$ vertices, $p$ be an arbitrary positive integer and $m$ be an integer such that $m\ge pn$. Then $ex(m, pG)\ge \max\{ex(m-pn+1, G)$$+{pn-1\choose 2}, ex(m-p+1, G)+(p-1)(m-p+1)\}$.

It is clear that $ex(n, S_\ell) = \lfloor\frac{(\ell-1)n}{2}\rfloor$. Lidický et al. ^[10] determined $ex(n, F)$ for $n$ sufficiently large, where $F$ is an arbitrary star forest. For $F = kS_\ell$, Lan et al. ^[8] determined $ex(n, kS_\ell)$ for $n\ge k(\ell^2+\ell+1)-\frac{\ell}{2}(\ell-3)$, Erdős and Gallai ^[4] determined $ex(n, kS_1)$ for all integers $k\ge 1$ and $n\ge 1$, Yuan and Zhang ^[14] determined $ex(n, kS_2)$ and characterized all extremal graphs for all integers $k\ge 1$ and $n\ge 1$ and Li et al. ^[9] determined $ex(n, kS_\ell)$ for all integers $k\ge 2$, $\ell\ge 3$ and $n\ge 1$. Gerbner et al. ^[6] investigate the function $ex(n, K_s, kF)$, where $F$ is a complete graph, cycle or a complete bipartite graph, although they focus on order of magnitude results. For a path $P_k$, Luo ^[11] obtained the upper bound of $ex{(n, K_s, P_k)}$, which is an extension of Erdős-Gallai Theorem ^[4], and Chakraborti and Chen ^[2] further determined $ex{(n, K_s, P_k)}$ for every $n$. Wang ^[13] determined $ex{(n, K_s, kP_2)}$, Zhu et al. ^[17] determined $ex{(n, K_s, H)}$ for $H$ to be an even linear forest and Zhu and Chen ^[16] further determined $ex(n, K_s, F)$, where $F$ is any linear forest and $n$ is sufficiently large. Moreover, Zhang et al. ^[15] determined the generalized Turán number of spanning linear forests. For a star $S_\ell$, Gan et al. ^[5] conjectured that any graph on $n$ vertices with maximum degree $\ell$ has at most $q{\ell\choose 3}+{r\choose 3}$ triangles, where $n = q\ell+r$ with $0\le r\le \ell-1$, in other words, $ex{(n, K_3, S_\ell)} = q{\ell\choose 3}+{r\choose 3}$. Moreover, Gan et al. ^[5] also showed their conjecture implies that $ex{(n, K_s, S_\ell)} = q{\ell\choose s}+{r\choose s}$ for any fixed $s\ge 4$. Chase ^[3] fully resolved the above Gan et al. conjecture as follows.

Theorem 1.2. ^[3] $ex(n, K_3, S_\ell) = q{\ell\choose 3}+{r \choose 3}$, where $n = q\ell+r$ with $0\le r\le \ell-1$. If $r\ge 3$, then $qK_\ell \cup K_r$ is the unique extremal graph. If $r < 3$, then $qK_\ell\cup H$ is an extremal graph, where $H$ is an arbitrary graph on $r$ vertices.

As mentioned above, Theorem 1.2, together with the work of Gan et al. ^[5], yields the general result, for cliques of any fixed size $s\ge 3$.

Theorem 1.3. ^[3,5] Let $s\ge 3$. Then $ex(n, K_s, S_\ell) = q{\ell \choose s}+{r \choose s}$, where $n = q\ell+r$ with $0\le r\le\ell-1$. If $r \ge s$, then $qK_\ell \cup K_r$ is the unique extremal graph. If $r < s$, then $qK_\ell \cup H$ is an extremal graph, where $H$ is an arbitrary graph on $r$ vertices.

In this paper, we determine $ex(n, K_s, 2S_\ell)$ for all integers $s\ge 4$, $\ell\ge 1$ and $n\ge 1$.

Theorem 1.4. Let $s \ge 4$.

(i) If $n\le 2\ell+1$, then $ex(n, K_s, 2S_\ell) = {n \choose s}$;

(ii) If $s \ge 2\ell+2$, then $ex(n, K_s, 2S_\ell) = 0$;

(iii) If $n\ge 2\ell+2$ and $s \le2 \ell+1$, let $n-1 = q\ell+r$ with $0 \le r \le \ell-1$, then

Note that we can obtain this lower bound of (ⅲ) of Theorem 1.4 by simply counting the number of copies of $K_s$ in the graphs $K_{2\ell+1} \cup ((q-2)K_\ell \cup K_r)$ and $K_1\vee(qK_\ell \cup K_r)$ which do not contain a copy of $2S_\ell$.

2.   Proof of Theorem 1.4

We first give three useful lemmas.

Lemma 2.1. Let $s \ge 4$ and $n-1 = q\ell+r$, where $0 \le r \le \ell-1$. Then ${\mathcal{N}}_s(K_1 \vee F)\le {\mathcal{N}}_s(K_1\vee (qK_\ell \cup K_r))$, where $F$ is an $S_\ell$-free graph on $n-1$ vertices.

Proof of Lemma 2.1. By Theorem 1.3, we can see that ${\mathcal{N}}_k(F) \le {\mathcal{N}}_k(qK_\ell \cup K_r)$ for all $k\ge 3$. Thus by $s-1\ge 3$, we have ${\mathcal{N}}_s(F) \le {\mathcal{N}}_s(qK_\ell \cup K_r)$ and ${\mathcal{N}}_{s-1}(F) \le {\mathcal{N}}_{s-1}(qK_\ell \cup K_r)$. This implies that

This completes the proof of Lemma 2.1. □

Lemma 2.2. ${n-1 \choose s}+{n-1 \choose {s-1}} = {n \choose s}$.

Proof of Lemma 2.2. It is trivial for $n\le s$. If $n > s$, then

This proves Lemma 2.2. □

Lemma 2.3. $\sum\limits_{i = 1}^{\ell+1}{\ell+i-1 \choose s-1} = {2\ell+1 \choose s}-{\ell \choose s}$.

Proof of Lemma 2.3. By Lemma 2.2, we have ${\ell+i \choose s} = {\ell+i-1 \choose s}+{\ell+i-1 \choose {s-1}}$ for all $i \in \{1, \dots, \ell+1\}$. Therefore,

This proves Lemma 2.3. □

Proof of Theorem 1.4. If $n\le 2\ell+1$, then we note that the extremal graph $K_n$ gives the lower and upper bounds for $ex(n, K_s, 2S_\ell)$, that is, $ex(n, K_s, 2S_\ell) = {n \choose s}$. If $s \ge 2\ell+2$, then $ex(n, K_s, 2S_\ell) = 0$. Otherwise, if $ex(n, K_s, 2S_\ell)\ge 1$, then there must be a copy of $K_s$ in $H$, where $H \in EX(n, K_s, 2S_\ell)$, implying that we can find a copy of $2S_\ell$ in $H$ by $s\ge 2\ell+2$, a contradiction. Now we only consider the case that $n\ge {2\ell+2}$ and $s\le 2\ell+1$. Recall that $n-1 = q\ell+r$, where $0 \le r \le \ell-1$. Then $n-2\ell-1 = (q-2)\ell+r$. Denote

Clearly, $ex(n, K_s, 2S_\ell)\ge f$. Let $G \in EX(n, K_s, 2S_\ell)$. Then ${\mathcal{N}}_s(G) = ex(n, K_s, 2S_\ell)$. We now prove that ${\mathcal{N}}_s(G)\le f$. To the contrary, we suppose that ${\mathcal{N}}_s(G)\ge f+1$. □

Claim 1. $\Delta(G)\ge \ell+1$.

Proof of Claim 1. Assume $\Delta(G)\le \ell$. Clearly, $G$ is an $S_{\ell+1}$-free graph. Let $n = q_1(\ell+1)+r_1$, where $0 \le r_1 \le \ell$. We can obtain that $n = q\ell+r+1 = q_1\ell+q_1+r_1$. Clearly, $q_1 \le q$.

Case 1. $q_1 = q$.

Then $r_1\le r+1$. We can obtain that

a contradiction.

Case 2. $q_1 < q$.

Then we have

a contradiction. This proves Claim 1. □

Claim 2. $\Delta(G)\le 2\ell$.

Proof of Claim 2. Suppose that $\Delta(G) \ge 2\ell+1$ and $d_G(u) = \Delta(G)$ for $u\in V(G)$. Then $d_G(v) \le \ell$ for any $v\in V(G)$ and $v \not = u$. Otherwise, if $d_G(v) > \ell$, then we can find two disjoint copies of $S_\ell$ in $G$ whose centers are $u$ and $v$ respectively, that is, $G$ contains a copy of $2S_\ell$, a contradiction. If $d_G(v) = \ell$ for $v\in V(G)$ and $v \not = u$, then $uv \in E(G)$. Otherwise, if $uv \notin E(G)$, then we can find two disjoint copies of $S_\ell$ in $G$ whose centers are $u$ and $v$ respectively, a contradiction. Thus $\Delta(G-u) < \ell$, and $G-u$ is an $S_\ell$-free graph. Recall that $n-1 = q\ell+r$, where $0 \le r \le \ell-1$. Then

By Lemma 2.1, we have

a contradiction, which proves Claim 2. □

Let $v_0\in V(G)$ and $d_G(v_0) = \Delta(G)$. Since $\ell+1 \le \Delta(G)\le 2\ell$, we can find a copy of $S_\ell$ (denoted by $F$) in $G$ whose center is $v_0$. Let $V(F) = \{v_0, v_1, \cdots, v_\ell \}$, $E(F) = \{v_0v_1, v_0v_2, \cdots, v_0v_\ell \}$ and $H = G-V(F)$. Let $x$ denote the number of $K_s$ with at least one vertex in $V(F)$.

Claim 3. $|N_G(v_i)\setminus \{v_0, v_1, \dots, v_\ell\}|\le \ell$ for all $i \in \{1, \cdots, \ell \}$.

Proof of Claim 3. Assume $|N_G(v_i)\setminus \{v_0, v_1, \dots, v_\ell\}| \ge \ell+1$ for some $i \in \{1, \cdots, \ell \}$. Let $v\in N_G(v_0)\setminus \{v_0, v_1, \dots, v_\ell\}$. Then we can find a copy of $S_\ell$ in $G[(V(F)\setminus \{v_i\}) \cup \{v\}]$ whose center is $v_0$. Due to $|N_G(v_i)\setminus \{v_0, v_1, \dots, v_\ell, v\}| \ge \ell+1-1 = \ell,$ we can find another copy of $S_\ell$ in $G[N_G(v_i)\setminus \{v_0, v_1, \dots, v_\ell, v\}]$ whose center is $v_i$. Therefore, $G$ contains a copy of $2S_\ell$, a contradiction. This proves Claim 3. □

Claim 4. $x \le {2\ell+1 \choose s}-{\ell \choose s}$.

Proof of Claim 4. The maximum number of copies of $K_s$ that contains $v_0$ is ${|N_G(v_0)| \choose {s-1}}$, and the maximum number of copies of $K_s$ that contains $v_i$ but does not contain any of $v_0, \cdots, v_{i-1}$ is ${{|N_G(v_i) \setminus \{v_0, \cdots, v_{i-1}\}| }\choose {s-1}}$ for $i = 1, \ldots, \ell$ in turn. By Claim 3, $|N_G(v_i)\setminus \{v_0, \cdots, v_{i-1}\}| = |N_G(v_i)\setminus \{v_0, v_1, \dots, v_\ell\}|+|N_F(v_i)\setminus \{v_0, \cdots, v_{i-1}\}|\le 2\ell-i$ for $i = 1, \ldots, \ell$. Moreover, $|N_G(v_0)|\le 2\ell$. Thus

Combining Lemma 2.3, we have

This proves Claim 4. □

Since $G$ is an $2{S_\ell}$-free graph, we have that $H$ is an $S_\ell$-free graph. Hence

By Claim 4 and ${\mathcal{N}}_s(G) = {\mathcal{N}}_s(H)+x$, then

a contradiction. Thus ${\mathcal{N}}_s(G) = f$. The proof of Theorem 1.4 is completed.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

Supported by Hainan Provincial Natural Science Foundation of China (No. 122RC545).

The authors would like to thank the referees for their helpful suggestions and comments.

Conflict of interest

The authors declare no conflict of interest.