# An extremal problem on potentially Kp,1,1-graphic sequences

Chunhui Lai

<figure><img src="image_1.png" /></figure>

► To cite this version:

Chunhui Lai. An extremal problem on potentially Kp,1,1-graphic sequences. Discrete Mathematics and Theoretical Computer Science, 2005, Vol. 7, pp.75-80. 10.46298/dmtcs.357 . hal-00959032

HAL Id: hal-00959032

https://inria.hal.science/hal-00959032

Submitted on 13 Mar 2014

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>
# An extremal problem on potentially $K_{p,1,1}$-graphic sequences†

Chunhui Lai

Department of Mathematics, Zhangzhou Teachers College, Zhangzhou, Fujian 363000, P. R. of CHINA.
E-mail: zjlaichu@public.zzptt.fj.cn

received Oct 4, 2004, revised Dec 23, 2004, Apr 21, 2005, accepted May 18, 2005.

A sequence $S$ is potentially $K_{p,1,1}$ graphical if it has a realization containing a $K_{p,1,1}$ as a subgraph, where $K_{p,1,1}$ is a complete 3-partite graph with partition sizes $p, 1, 1$. Let $\sigma(K_{p,1,1}, n)$ denote the smallest degree sum such that every $n$-term graphical sequence $S$ with $\sigma(S) \ge \sigma(K_{p,1,1}, n)$ is potentially $K_{p,1,1}$ graphical. In this paper, we prove that $\sigma(K_{p,1,1}, n) \ge 2[(p+1)(n-1)+2]/2$ for $n \ge p+2$. We conjecture that equality holds for $n \ge 2p+4$. We prove that this conjecture is true for $p=3$.

AMS Subject Classifications: 05C07, 05C35

**Keywords:** graph; degree sequence; potentially $K_{p,1,1}$-graphic sequence

## 1 Introduction

If $S = (d_1, d_2, \dots, d_n)$ is a sequence of non-negative integers, then it is called graphical if there is a simple graph $G$ of order $n$, whose degree sequence $(d(v_1), d(v_2), \dots, d(v_n))$ is precisely $S$. If $G$ is such a graph then $G$ is said to realize $S$ or be a realization of $S$. A graphical sequence $S$ is potentially $H$ graphical if there is a realization of $S$ containing $H$ as a subgraph, while $S$ is forcibly $H$ graphical if every realization of $S$ contains $H$ as a subgraph. Let $\sigma(S) = d(v_1) + d(v_2) + \dots + d(v_n)$, and $[x]$ denote the largest integer less than or equal to $x$. We denote $G+H$ as the graph with $V(G+H) = V(G) \cup V(H)$ and $E(G+H) = E(G) \cup E(H) \cup \{xy : x \in V(G), y \in V(H)\}$. Let $K_k$, and $C_k$ denote a complete graph on $k$ vertices, and a cycle on $k$ vertices, respectively. Let $K_{p,1,1}$ denote a complete 3-partite graph with partition sizes $p, 1, 1$.

Given a graph $H$, what is the maximum number of edges of a graph with $n$ vertices not containing $H$ as a subgraph? This number is denoted $ex(n, H)$, and is known as the Turán number. This problem was proposed for $H = C_4$ by Erdős [3] in 1938 and in general by Turán [12]. In terms of graphic sequences, the number $2ex(n, H)+2$ is the minimum even integer $l$ such that every $n$-term graphical sequence $S$ with

<footnote>†Project Supported by NNSF of China(10271105), NSF of Fujian, Science and Technology Project of Fujian, Fujian Provincial Training Foundation for "Bai-Quan-Wan Talents Engineering", Project of Fujian Education Department and Project of Zhangzhou Teachers College.</footnote>
$\sigma(S) \ge l$ is forcibly $H$ graphical. Here we consider the following variant: determine the minimum even integer $l$ such that every $n$-term graphical sequence $S$ with $\sigma(S) \ge l$ is potentially $H$ graphical. We denote this minimum $l$ by $\sigma(H, n)$. Erdős, Jacobson and Lehel [4] showed that $\sigma(K_k, n) \ge (k-2)(2n-k+1)+2$ and conjectured that equality holds. They proved that if $S$ does not contain zero terms, this conjecture is true for $k=3, n \ge 6$. The conjecture is confirmed in [5], [7], [8], [9] and [10].

Gould, Jacobson and Lehel [5] also proved that $\sigma(pK_2, n) = (p-1)(2n-2)+2$ for $p \ge 2$; $\sigma(C_4, n) = 2[\frac{3n-1}{2}]$ for $n \ge 4$. Luo [11] characterized the potentially $C_k$ graphic sequence for $k=3, 4, 5$. Yin and Li [13] gave sufficient conditions for a graphic sequence being potentially $K_{r,s}$-graphic, and determined $\sigma(K_{r,r}, n)$ for $r=3, 4$. Lai [6] proved that $\sigma(K_4 - e, n) = 2[\frac{3n-1}{2}]$ for $n \ge 7$. In this paper, we prove that $\sigma(K_{p,1,1}, n) \ge 2[(p+1)(n-1)+2]/2$ for $n \ge p+2$. We conjecture that equality holds for $n \ge 2p+4$. We prove that this conjecture is true for $p=3$.

## 2 Main results.

**Theorem 1** $\sigma(K_{p,1,1}, n) \ge 2[(p+1)(n-1)+2]/2$, for $n \ge p+2$.

**Proof:** If $p=1$, by Erdős, Jacobson and Lehel [4], $\sigma(K_{1,1,1}, n) \ge 2n$, Theorem 1 is true.

If $p=2$, by Gould, Jacobson and Lehel [5], $\sigma(K_{2,1,1}, n) = \sigma(K_4 - e, n) \ge \sigma(C_4, n) = 2[(3n-1)/2]$, Theorem 1 is true. Then we can suppose that $p \ge 3$.

We first consider odd $p$. If $n$ is odd, let $n = 2m+1$, by Theorem 9.7 of [2], $K_{2m}$ is the union of one 1-factor $M$ and $m-1$ spanning cycles $C_1^1, C_2^1, \dots, C_{m-1}^1$. Let

$$H = C_1^1 \cup C_2^1 \cup \dots \cup C_{\frac{p-1}{2}}^1 + K_1 \quad (1)$$

Then $H$ is a realization of $((n-1)^1, p^{n-1})$, where the symbol $x^y$ stands for $y$ consecutive terms $x$. Since $K_{p,1,1}$ contains two vertices of degree $p+1$ while $((n-1)^1, p^{n-1})$ only contains one integer $n-1$ greater than degree $p$, $((n-1)^1, p^{n-1})$ is not potentially $K_{p,1,1}$ graphic. Thus

$$\sigma(K_{p,1,1}, n) \ge (n-1) + p(n-1) + 2 = 2[(p+1)(n-1)+2]/2. \quad (2)$$

Next, if $n$ is even, let $n = 2m+2$, by Theorem 9.6 of [2], $K_{2m+1}$ is the union of $m$ spanning cycles $C_1^1, C_2^1, \dots, C_m^1$. Let

$$H = C_1^1 \cup C_2^1 \cup \dots \cup C_{\frac{p-1}{2}}^1 + K_1 \quad (3)$$

Then $H$ is a realization of $((n-1)^1, p^{n-1})$, and we are done as before. This completes the discussion for odd $p$.

Now we consider even $p$. If $n$ is odd, let $n = 2m+1$, by Theorem 9.7 of [2], $K_{2m}$ is the union of one 1-factor $M$ and $m-1$ spanning cycles $C_1^1, C_2^1, \dots, C_{m-1}^1$. Let

$$H = M \cup C_1^1 \cup C_2^1 \cup \dots \cup C_{\frac{p-2}{2}}^1 + K_1 \quad (4)$$

Then $H$ is a realization of $((n-1)^1, p^{n-1})$, and we are done as before.
Next, if $n$ is even, let $n = 2m + 2$, by Theorem 9.6 of [2], $K_{2m+1}$ is the union of $m$ spanning cycles $C_1^1, C_2^1, \dots, C_m^1$. Let

$$C_1^1 = x_1x_2\dots x_{2m+1}x_1 \\ H = (C_1^1 \cup C_2^1 \cup \dots \cup C_{\frac{p}{2}}^1 + K_1) - \{x_1x_2, x_3x_4, \dots, x_{2m-1}x_{2m}, x_{2m+1}x_1\}$$

Then $H$ is a realization of $((n-1)^1, p^{n-2}, (p-1)^1)$. It is easy to see that $((n-1)^1, p^{n-2}, (p-1)^1)$ is not potentially $K_{p,1,1}$ graphic. Thus

$$\sigma(K_{p,1,1}, n) \geq (n-1) + p(n-2) + p-1 + 2 \\ = 2[(p+1)(n-1) + 2]/2.$$

This completes the discussion for even $p$, and so finishes the proof of Theorem 1 □

**Theorem 2** For $n = 5$ and $n \geq 7$,

$$\sigma(K_{3,1,1}, n) = 4n - 2.$$

For $n = 6$, if $S$ is a 6-term graphical sequence with $\sigma(S) \geq 22$, then either there is a realization of $S$ containing $K_{3,1,1}$ or $S = (4^6)$. (Thus $\sigma(K_{3,1,1}, 6) = 26$.)

**Proof:** By Theorem 1, for $n \geq 5$, $\sigma(K_{3,1,1}, n) \geq 2[(3+1)(n-1)+2]/2 = 4n-2$. We need to show that if $S$ is an $n$-term graphical sequence with $\sigma(S) \geq 4n-2$, then there is a realization of $S$ containing a $K_{3,1,1}$ (unless $S = (4^6)$). Let $d_1 \geq d_2 \geq \dots \geq d_n$, and let $G$ be a realization of $S$.

**Case $n = 5$:** If a graph has size $q \geq 9$, then clearly it contains a $K_{3,1,1}$, so that $\sigma(K_{3,1,1}, 5) \leq 4n-2$.

**Case $n = 6$:** If $\sigma(S) = 22$, we first consider $d_6 \leq 2$. Let $S'$ be the degree sequence of $G - v_6$, so $\sigma(S') \geq 22 - 2 \times 2 = 18$. Then $S'$ has a realization containing a $K_{3,1,1}$. Therefore $S$ has a realization containing a $K_{3,1,1}$. Now we consider $d_6 \geq 3$. It is easy to see that $S$ is one of $(5^2, 3^4)$, $(5^1, 4^2, 3^3)$ or $(4^4, 3^2)$. Obviously, all of them are potentially $K_{3,1,1}$-graphic. Next, if $\sigma(S) = 24$, we first consider $d_6 \leq 3$. Let $S'$ be the degree sequence of $G - v_6$, so $\sigma(S') \geq 24 - 3 \times 2 = 18$. Then $S'$ has a realization containing a $K_{3,1,1}$. Therefore $S$ has a realization containing a $K_{3,1,1}$. Now we consider $d_6 \geq 4$. It is easy to see that $S = (4^6)$. Obviously, $(4^6)$ is graphical and $(4^6)$ is not potentially $K_{3,1,1}$ graphic. Finally, suppose that $\sigma(S) \geq 26$. We first consider $d_6 \leq 4$. Let $S'$ be the degree sequence of $G - v_6$, so $\sigma(S') \geq 26 - 2 \times 4 = 18$. Then $S'$ has a realization containing a $K_{3,1,1}$. Therefore $S$ has a realization containing a $K_{3,1,1}$. Now we consider $d_6 \geq 5$. It is easy to see that $S = (5^6)$. Obviously, $(5^6)$ is potentially $K_{3,1,1}$-graphic.

**Case $n = 7$:** First we assume that $\sigma(S) = 26$. Suppose $d_7 \leq 2$ and let $S'$ be the degree sequence of $G - v_7$, so $\sigma(S') \geq 26 - 2 \times 2 = 22$. Then $S'$ has a realization containing a $K_{3,1,1}$ or $S' = (4^6)$. Therefore $S$ has a realization containing a $K_{3,1,1}$ or $S = (5^1, 4^5, 1^1)$. Obviously, $(5^1, 4^5, 1^1)$ is potentially $K_{3,1,1}$-graphic. In either event, $S$ has a realization containing a $K_{3,1,1}$. Now we assume that $d_7 \geq 3$. It is easy to see that $S$ is one of $(6^1, 5^1, 3^5), (6^1, 4^2, 3^4), (5^2, 4^1, 3^4), (5^1, 4^3, 3^3)$ or $(4^5, 3^2)$. Obviously, all of them are potentially $K_{3,1,1}$-graphic. Next, if $\sigma(S) = 28$, Suppose $d_7 \leq 3$. Let $S'$ be the degree sequence of $G - v_7$, so $\sigma(S') \geq 28 - 3 \times 2 = 22$. Then
$S'$ has a realization containing a $K_{3,1,1}$ or $S' = (4^6)$. Therefore $S$ has a realization containing a $K_{3,1,1}$ or $S = (5^2, 4^4, 2^1)$. Obviously, $(5^2, 4^2, 2^1)$ is potentially $K_{3,1,1}$-graphic. In either event, $S$ has a realization containing a $K_{3,1,1}$. Now we assume that $d_7 \ge 4$, then $S = (4^7)$. Clearly, $(4^7)$ has a realization containing a $K_{3,1,1}$. Finally, suppose that $\sigma(S) \ge 30$. If $d_7 \le 4$. Let $S'$ be the degree sequence of $G - v_7$, so $\sigma(S') \ge 30 - 2 \times 4 = 22$. Then $S'$ has a realization containing a $K_{3,1,1}$ or $S' = (4^6)$. Therefore $S$ has a realization containing a $K_{3,1,1}$ or $S = (5^3, 4^3, 3^1)$. Clearly, $(5^3, 4^3, 3^1)$ has a realization containing a $K_{3,1,1}$. In either event, $S$ has a realization containing a $K_{3,1,1}$. Now we consider $d_7 \ge 5$. It is easy to see that $\sigma(S) \ge 5 \times 7 = 35$. Obviously $\sigma(S) \ge 36$. Clearly, $S$ has a realization containing a $K_{3,1,1}$.

We proceed by induction on $n$. Take $n \ge 8$ and make the inductive assumption that for $7 \le t < n$, whenever $S_1$ is a $t$-term graphical sequence such that

$$ \sigma(S_1) \ge 4t - 2 \qquad (5) $$

then $S_1$ has a realization containing a $K_{3,1,1}$. Let $S$ be an $n$-term graphical sequence with $\sigma(S) \ge 4n - 2$. If $d_n \le 2$, let $S'$ be the degree sequence of $G - v_n$. Then $\sigma(S') \ge 4n - 2 - 2 \times 2 = 4(n - 1) - 2$. By induction, $S'$ has a realization containing a $K_{3,1,1}$. Therefore $S$ has a realization containing a $K_{3,1,1}$. Hence, we may assume that $d_n \ge 3$. By Proposition 2 and Theorem 4 of [5] (or Theorem 3.3 of [7]) $S$ has a realization containing a $K_4$. By Lemma 1 of [5], there is a realization $G$ of $S$ with $v_1, v_2, v_3, v_4$, the four vertices of highest degree containing a $K_4$. If $d(v_2) = 3$, then $4n - 2 \le \sigma(S) \le n - 1 + 3(n - 1) = 4n - 4$. This is a contradiction. Hence, we may assume that $d(v_2) \ge 4$. Let $v_1$ be adjacent to $v_2, v_3, v_4, y_1$. If $y_1$ is adjacent to one of $v_2, v_3, v_4$, then $G$ contains a $K_{3,1,1}$. Hence, we may assume that $y_1$ is not adjacent to $v_2, v_3, v_4$. Let $v_2$ be adjacent to $v_1, v_3, v_4, y_2$. If $y_2$ is adjacent to one of $v_1, v_3, v_4$, then $G$ contains a $K_{3,1,1}$. Hence, we may assume that $y_2$ is not adjacent to $v_1, v_3, v_4$. Since $d(y_1) \ge d_n \ge 3$, there is a new vertex $y_3$, such that $y_1y_3 \in E(G)$.

**Case 1:** Suppose $y_3v_3 \in E(G)$. If $y_3v_4 \in E(G)$, then $G$ contains a $K_{3,1,1}$. Hence, we may assume that $y_3v_4 \notin E(G)$. Then the edge interchange that removes the edges $y_1y_3, v_3v_4$ and $v_2y_2$ and inserts the edges $y_1v_2, y_3v_4$ and $y_2v_3$ produces a realization $G'$ of $S$ containing a $K_{3,1,1}$.

**Case 2:** Suppose $y_3v_3 \notin E(G)$. Then the edge interchange that removes the edges $y_1y_3, v_3v_4$ and $v_2y_2$ and inserts the edges $y_1v_2, y_3v_3$ and $y_2v_4$ produces a realization $G'$ of $S$ containing a $K_{3,1,1}$.

This finishes the inductive step, and thus Theorem 2 is established. $\square$
We make the following conjecture:

**Conjecture 1** $\sigma(K_{p,1,1}, n) = 2[(p+1)(n-1)+2]/2$, for $n \ge 2p+4$.

This conjecture is true for $p=1$, by Theorem 3.5 of [4], for $p=2$, by Theorem 1 of [6], and for $p=3$, by the above Theorem 2.

Acknowledgements

The author thanks Prof. Therese Biedl for her valuable suggestions. The author thanks the referees for many helpful comments.

References

[1] B. Bollobás, *Extremal Graph Theory*, Academic Press, London, 1978.

[2] F. Harary, *Graph Theory*, Addison-Wesley Publishing Co., 1969.

[3] P. Erdős, On sequences of integers no one of which divides the product of two others and some related problems, *Izv. Naustno-Issl. Mat. i Meh. Tomsk* 2, 1938, p. 74–82.

[4] P. Erdős, M.S. Jacobson and J. Lehel, Graphs realizing the same degree sequences and their respective clique numbers, in *Graph Theory, Combinatorics and Application*, Vol. 1(Y. Alavi et al., eds.), John Wiley and Sons, Inc., New York, 1991, p. 439–449.

[5] R.J. Gould, M.S. Jacobson and J. Lehel, Potentially $G$-graphic degree sequences, in *Combinatorics, Graph Theory and Algorithms, Vol. 2* (Y. Alavi et al., eds.), New Issues Press, Kalamazoo, MI, 1999, p. 451–460.

[6] Lai Chunhui, A note on potentially $K_4 - e$ graphical sequences, *Australasian J. of Combinatorics* 24, 2001, p. 123–127.

[7] Li Jiong-Sheng and Song Zi-Xia, An extremal problem on the potentially $P_k$-graphic sequences, *Discrete Math.* 212, 2000, p. 223–231.

[8] Li Jiong-Sheng and Song Zi-Xia, The smallest degree sum that yields potentially $P_k$-graphical sequences, *J. Graph Theory* 29, 1998, p. 63–72.

[9] Li Jiong-Sheng and Song Zi-Xia, On the potentially $P_k$-graphic sequences, *Discrete Math.* 195, 1999, p. 255–262.

[10] Li Jiong-Sheng, Song Zi-Xia and Luo Rong, The Erdős-Jacobson-Lehel conjecture on potentially $P_k$-graphic sequence is true, *Science in China (Series A)*, 41:5, 1998, p. 510–520.

[11] Rong Luo, On potentially $C_k$-graphic sequences, *Ars Combinatoria* 64, 2002, p. 301–318.

[12] P. Turán, On an extremal problem in graph theory, *Mat. Fiz. Lapok* 48, 1941, p. 436–452.

[13] Yin Jian-Hua and Li Jiong-Sheng, An extremal problem on potentially $K_{r,s}$-graphic sequences, *Discrete Math.* 260, 2003, p. 295–305.