Potentially $K_m-G$-graphical sequences: A survey

Lai, Chunhui   ; Hu, Lili

Czechoslovak Mathematical Journal, Tome 59 (2009) no. 4, pp. 1059-1075

Abstract (VO)

The set of all non-increasing nonnegative integer sequences $\pi =$ ($d(v_1 ),d(v_2 ), \dots , d(v_n )$) is denoted by ${\rm NS}_n$. A sequence $\pi \in {\rm NS}_n$ is said to be graphic if it is the degree sequence of a simple graph $G$ on $n$ vertices, and such a graph $G$ is called a realization of $\pi $. The set of all graphic sequences in ${\rm NS}_n$ is denoted by ${\rm GS}_n$. A graphical sequence $\pi $ is potentially $H$-graphical if there is a realization of $\pi $ containing $H$ as a subgraph, while $\pi $ is forcibly $H$-graphical if every realization of $\pi $ contains $H$ as a subgraph. Let $K_k$ denote a complete graph on $k$ vertices. Let $K_m-H$ be the graph obtained from $K_m$ by removing the edges set $E(H)$ of the graph $H$ ($H$ is a subgraph of $K_m$). This paper summarizes briefly some recent results on potentially $K_m-G$-graphic sequences and give a useful classification for determining $\sigma (H,n)$.

Détail

Classification : 05C07, 05C35
Keywords: graph; degree sequence; potentially $K_m-G$-graphic sequences

Bibliographie

[1] Bollobás, B.: Extremal Graph Theory. Academic Press, London (1978). | MR

[2] Chen, Gang: Potentially $C\sb 6$-graphic sequences. J. Guangxi Univ. Nat. Sci. Ed. 28 (2003), 119-124. | MR

[3] Chen, Gang: Characterize the potentially $K_{1,2,2}$-graphic sequences. Journal of Qingdao University of Science and Technology 27 (2006), 86-88.

[4] Chen, Gang: The smallest degree sum that yields potentially fan graphical sequences. J. Northwest Norm. Univ., Nat. Sci. 42 (2006), 27-30. | MR | Zbl

[5] Chen, Gang: An extremal problem on potentially $K_{r,s,t}$-graphic sequences. J. YanTai University 19 (2006), 245-252. | MR

[6] Chen, Gang: Potentially $K_{3,s}-ke$ graphical sequences. Guangxi Sciences 13 (2006), 164-171.

[7] Chen, Gang: A note on potentially $K_{1,1,t}$-graphic sequences. Australasian J. Combin. 37 (2007), 21-26. | MR | Zbl

[8] Chen, Gang, Li, Xining: On potentially $K_{1,t}+e$-graphic sequences. J. Zhangzhou Teach. Coll. 20 (2007), 5-7. | MR | Zbl

[9] Chen, Gang, Yin, Jianhua: The smallest degree sum that yields potentially $W_5$-graphic sequences. J. XuZhou Normal University 21 (2003), 5-7. | MR | Zbl

[10] Chen, Gang, Yin, Jianhua, Fan, Yingmei: Potentially $\sb kC\sb 6$-graphic sequences. J. Guangxi Norm. Univ. Nat. Sci. 24 (2006), 26-29. | MR

[11] Chen, Guantao, Ferrara, Michael, Gould, Ronald J., Schmitt, John R.: Graphic sequences with a realization containing a complete multipartite subgraph, accepted by Discrete Mathematics.

[12] Erdös, P., Gallai, T.: Graphs with given degrees of vertices. Math. Lapok 11 (1960), 264-274.

[13] Erdös, P., Jacobson, M. S., Lehel, J.: Graphs realizing the same degree sequences and their respective clique numbers. Graph Theory Combinatorics and Application, Vol. 1 (Y. Alavi et al., eds.), John Wiley and Sons, Inc., New York (1991), 439-449. | MR

[14] Eschen, Elaine M., Niu, Jianbing: On potentially $K_4-e$-graphic sequences. Australasian J. Combin. 29 (2004), 59-65. | MR | Zbl

[15] Ferrara, Michael J.: Graphic sequences with a realization containing a union of cliques. Graphs and Combinatorics 23 (2007), 263-269. | DOI | MR | Zbl

[16] Ferrara, M., Gould, R., Schmitt, J.: Potentially $K_s^t$-graphic degree sequences, submitted.

[17] Ferrara, M., Gould, R., Schmitt, J.: Graphic sequences with a realization containing a friendship graph. Ars Combinatoria 85 (2007), 161-171. | MR

[18] Ferrara, M., Jacobson, M., Schmitt, J., Siggers, M.: Potentially $H$-bigraphic sequences, submitted.

[19] Gould, Ronald J., Jacobson, Michael S., Lehel, J.: Potentially $G$-graphical degree sequences. Combinatorics, graph theory, and algorithms, Vol. I, II (Kalamazoo, MI, 1996), 451-460, New Issues Press, Kalamazoo, MI, 1999. | MR

[20] Gupta, Gautam, Joshi, Puneet, Tripathi, Amitabha: Graphic sequences of trees and a problem of Frobenius. Czech. Math. J. 57 (2007), 49-52. | DOI | MR | Zbl

[21] Hu, Lili, Lai, Chunhui: On potentially $K_5-C_4$-graphic sequences, accepted by Ars Combinatoria.

[22] Hu, Lili, Lai, Chunhui: On potentially $K_5-Z_4$-graphic sequences, submitted.

[23] Hu, Lili, Lai, Chunhui: On potentially $K_5-E_3$-graphic sequences, accepted by Ars Combinatoria.

[24] Hu, Lili, Lai, Chunhui: On Potentially 3-regular graph graphic Sequences, accepted by Utilitas Mathematica.

[25] Hu, Lili, Lai, Chunhui, Wang, Ping: On potentially $K_5-H$-graphic sequences, accepted by Czech. Math. J.

[26] Huang, Qin: On potentially $K_m-e$-graphic sequences. J. ZhangZhou Teachers College 15 (2002), 26-28. | MR

[27] Huang, Qin: On potentially $K_5-e$-graphic sequences. J. XinJiang University 22 (2005), 276-284. | MR

[28] Kleitman, D. J., Wang, D. L.: Algorithm for constructing graphs and digraphs with given valences and factors. Discrete Math. 6 (1973), 79-88. | DOI | MR

[29] Lai, Chunhui: On potentially $C_k$-graphic sequences. J. ZhangZhou Teachers College 11 (1997), 27-31.

[30] Lai, Chunhui: A note on potentially $K_4-e$ graphical sequences. Australasian J. of Combinatorics 24 (2001), 123-127. | MR | Zbl

[31] Lai, Chunhui: Characterize the potentially $K_4-e$ graphical sequences. J. ZhangZhou Teachers College 15 (2002), 53-59. | MR

[32] Lai, Chunhui: The Smallest Degree Sum that Yields Potentially $C_k$-graphic Sequences. J. Combin. Math. Combin. Comput. 49 (2004), 57-64. | MR

[33] Lai, Chunhui: An extremal problem on potentially $K_{p,1,\cdots,1}$-graphic sequences. J. Zhangzhou Teachers College 17 (2004), 11-13. | MR

[34] Lai, Chunhui: An extremal problem on potentially $K_{p,1,1}$-graphic sequences. Discrete Mathematics and Theoretical Computer Science 7 (2005), 75-80. | MR | Zbl

[35] Lai, Chunhui: An extremal problem on potentially $K_m-C_4$-graphic sequences. Journal of Combinatorial Mathematics and Combinatorial Computing 61 (2007), 59-63. | MR | Zbl

[36] Lai, Chunhui: An extremal problem on potentially $K_m-P_k$-graphic sequences, accepted by International Journal of Pure and Applied Mathematics.

[37] Lai, Chunhui: The smallest degree sum that yields potentially $K_{r+1}-Z$-graphical Sequences, accepted by Ars Combinatoria.

[38] Lai, Chunhui, Hu, Lili: An extremal problem on potentially $K_{r+1}-H$-graphic sequences, accepted by Ars Combinatoria.

[39] Lai, Chunhui, Sun, Yuzhen: An extremal problem on potentially $K_{r+1}-(kP_2\cup tK_2)$-graphic sequences. International Journal of Applied Mathematics & Statistics 14 (2009), 30-36. | MR

[40] Lai, Chunhui, Yan, Guiying: On potentially $K_{r+1}-U$-graphical Sequences, accepted by Utilitas Mathematica.

[41] Li, Jiongsheng, Luo, Rong: Potentially $_3C_l$-Graphic Sequences. J. Univ. Sci. Technol. China 29 (1999), 1-8. | MR

[42] Li, Jiongsheng, Luo, Rong, Liu, Yunkai: An extremal problem on potentially $_3C_l$-graphic sequences. J. Math. Study 31 (1998), 362-369. | MR | Zbl

[43] Li, Jiongsheng, Song, Zi-xia: The smallest degree sum that yields potentially $P_k$-graphical sequences. J. Graph Theory 29 (1998), 63-72. | DOI | MR

[44] Li, Jiongsheng, Song, Zi-xia: On the potentially $P_k$-graphic sequences. Discrete Math. 195 (1999), 255-262. | MR

[45] Li, Jiongsheng, Song, Zi-xia: An extremal problem on the potentially $P_k$-graphic sequences. Discrete Math. 212 (2000), 223-231. | DOI | MR

[46] Li, Jiongsheng, Song, Zi-xia, Luo, Rong: The Erdös-Jacobson-Lehel conjecture on potentially $P_k$-graphic sequence is true. Science in China (Series A) 41 (1998), 510-520. | DOI | MR

[47] Li, Jiongsheng, Song, Zi-xia, Wang, Ping: The Erdos-Jacobson-Lehel conjecture about potentially $P\sb k$-graphic sequences. J. China Univ. Sci. Tech. 28 (1998), 1-9. | MR

[48] Li, Jiongsheng, Yin, Jianhua: Avariation of an extremal theorem due to Woodall. Southeast Asian Bull. Math. 25 (2001), 427-434. | DOI | MR

[49] Li, Jiongsheng, Yin, Jianhua: On potentially $A\sb {r,s}$-graphic sequences. J. Math. Study 34 (2001), 1-4. | MR

[50] Li, Jiongsheng, Yin, Jianhua: Extremal graph theory and degree sequences. Adv. Math. 33 (2004), 273-283. | MR

[51] Li, Jiong Sheng, Yin, Jianhua: The threshold for the Erdos, Jacobson and Lehel conjecture to be true. Acta Math. Sin. (Engl. Ser.) 22 (2006), 1133-1138. | DOI | MR

[52] Liu, Mingjing, Hu, Lili: On Potentially $K_5-Z_5$ graphic sequences. J. Zhangzhou Normal University 57 (2007), 20-24. | MR

[53] Luo, Rong: On potentially $C_k$-graphic sequences. Ars Combinatoria 64 (2002), 301-318. | MR

[54] Luo, Rong, Warner, Morgan: On potentially $K_k$-graphic sequences. Ars Combin. 75 (2005), 233-239. | MR | Zbl

[55] Mubayi, Dhruv: Graphic sequences that have a realization with large clique number. J. Graph Theory 34 (2000), 20-29. | MR | Zbl

[56] Schmitt, J. R., Ferrara, M.: An Erdös-Stone Type Conjecture for Graphic Sequences. Electronic Notes in Discrete Mathematics 28 (2007), 131-135. | DOI | MR

[57] Xu, Zhenghua, Hu, Lili: Characterize the potentially $K_{1,4}+e$ graphical sequences. ZhangZhou Teachers College 55 (2007), 4-8. | MR

[58] Yin, Jianhua: The smallest degree sum that yields potentially $K_{1,1,3}$-graphic sequences. J. HaiNan University 22 (2004), 200-204. | MR

[59] Yin, Jianhua: Some new conditions for a graphic sequence to have a realization with prescribed clique size, submitted.

[60] Yin, Jianhua, Chen, Gang, Chen, Guoliang: On potentially $\sb kC\sb l$-graphic sequences. J. Combin. Math. Combin. Comput. 61 (2007), 141-148. | MR

[61] Yin, Jianhua, Chen, Gang: On potentially $K_{r_1,r_2,\cdots,r_m}$-graphic sequences. Util. Math. 72 (2007), 149-161. | MR

[62] Yin, Jianhua, Chen, Gang, Schmitt, John R.: Graphic Sequences with a realization containing a generalized Friendship Graph. Discrete Mathematics 308 (2008), 6226-6232. | DOI | MR

[63] Yin, Jianhua, Li, Jiongsheng: The smallest degree sum that yields potentially $K_{r,r}$-graphic sequences. Science in China Ser A (2002), 45 694-705. | MR | Zbl

[64] Yin, Jianhua, Li, Jiongsheng: On the threshold in the Erdos-Jacobson-Lehel problem. Math. Appl. 15 (2002), 123-128. | MR

[65] Yin, Jianhua, Li, Jiongsheng: An extremal problem on the potentially $K_{r,s}$-graphic sequences. Discrete Math. (2003), 260 295-305. | MR

[66] Yin, Jianhua, Li, Jiongsheng: Two sufficient conditions for a graphic sequence to have a realization with prescribed clique size. Discrete Math. 301 (2005), 218-227. | DOI | MR

[67] Yin, Jianhua, Li, Jiongsheng: Potentially $K_{r_1,r_2,\cdots,r_l,r,s}$-graphic sequences. Discrete Mathematics 307 (2007), 1167-1177. | DOI | MR

[68] Yin, Jianhua, Li, Jiongsheng, Chen, Guoliang: The smallest degree sum that yields potentially $_3C_l$-graphic sequences. Discrete Mathematics 270 (2003), 319-327. | DOI | MR

[69] Yin, Jianhua, Li, Jiongsheng, Chen, Guoliang: A variation of a classical Turn-type extremal problem. Eur. J. Comb. 25 (2004), 989-1002. | DOI | MR

[70] Yin, Jianhua, Li, Jiongsheng, Chen, Guoliang: The smallest degree sum that yields potentially $K_{2,s}$-graphic sequences. Ars Combinatoria 74 (2005), 213-222. | MR

[71] Yin, Jianhua, Li, Jiongsheng, Mao, Rui: An extremal problem on the potentially $K_{r+1}-e$-graphic sequences. Ars Combinatoria 74 (2005), 151-159. | MR

[72] Yin, Mengxiao: The smallest degree sum that yields potentially $K_{r+1}-K_3$-graphic sequences. Acta Math. Appl. Sin. Engl. Ser. 22 (2006), 451-456. | DOI | MR | Zbl

[73] Yin, Mengxiao, Yin, Jianhua: On potentially $H$-graphic sequences. Czech. Math. J. 57 (2007), 705-724. | DOI | MR