Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
graph; degree sequence; potentially $K_m-G$-graphic sequences
graph; degree sequence; potentially $K_m-G$-graphic sequences
Summary:
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)$.
References:
[1] Bollobás, B.: Extremal Graph Theory. Academic Press, London (1978). MR 0506522
[2] Chen, Gang: Potentially $C\sb 6$-graphic sequences. J. Guangxi Univ. Nat. Sci. Ed. 28 (2003), 119-124. MR 1997256
[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 2253937 | Zbl 1103.05302
[5] Chen, Gang: An extremal problem on potentially $K_{r,s,t}$-graphic sequences. J. YanTai University 19 (2006), 245-252. MR 2260663
[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 2284364 | Zbl 1121.05034
[8] Chen, Gang, Li, Xining: On potentially $K_{1,t}+e$-graphic sequences. J. Zhangzhou Teach. Coll. 20 (2007), 5-7. MR 2668610 | Zbl 1174.05339
[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 1987158 | Zbl 1036.05501
[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 2259980
[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 1170797
[14] Eschen, Elaine M., Niu, Jianbing: On potentially $K_4-e$-graphic sequences. Australasian J. Combin. 29 (2004), 59-65. MR 2037333 | Zbl 1049.05027
[15] Ferrara, Michael J.: Graphic sequences with a realization containing a union of cliques. Graphs and Combinatorics 23 (2007), 263-269. DOI 10.1007/s00373-007-0737-9 | MR 2320581 | Zbl 1123.05028
[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 2359288
[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 1985076
[20] Gupta, Gautam, Joshi, Puneet, Tripathi, Amitabha: Graphic sequences of trees and a problem of Frobenius. Czech. Math. J. 57 (2007), 49-52. DOI 10.1007/s10587-007-0042-z | MR 2309947 | Zbl 1174.05023
[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 1952471
[27] Huang, Qin: On potentially $K_5-e$-graphic sequences. J. XinJiang University 22 (2005), 276-284. MR 2175912
[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 10.1016/0012-365X(73)90037-X | MR 0327559
[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 1852813 | Zbl 0983.05025
[31] Lai, Chunhui: Characterize the potentially $K_4-e$ graphical sequences. J. ZhangZhou Teachers College 15 (2002), 53-59. MR 1709888
[32] Lai, Chunhui: The Smallest Degree Sum that Yields Potentially $C_k$-graphic Sequences. J. Combin. Math. Combin. Comput. 49 (2004), 57-64. MR 2054962
[33] Lai, Chunhui: An extremal problem on potentially $K_{p,1,\cdots,1}$-graphic sequences. J. Zhangzhou Teachers College 17 (2004), 11-13. MR 2164060
[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 2164060 | Zbl 1153.05021
[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 2322201 | Zbl 1139.05016
[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 2524881
[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 1707604
[42] Li, Jiongsheng, Luo, Rong, Liu, Yunkai: An extremal problem on potentially $_3C_l$-graphic sequences. J. Math. Study 31 (1998), 362-369. MR 1685466 | Zbl 0920.05043
[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 10.1002/(SICI)1097-0118(199810)29:2<63::AID-JGT2>3.0.CO;2-A | MR 1644418
[44] Li, Jiongsheng, Song, Zi-xia: On the potentially $P_k$-graphic sequences. Discrete Math. 195 (1999), 255-262. MR 1663863
[45] Li, Jiongsheng, Song, Zi-xia: An extremal problem on the potentially $P_k$-graphic sequences. Discrete Math. 212 (2000), 223-231. DOI 10.1016/S0012-365X(99)00289-7 | MR 1748652
[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 10.1007/BF02879940 | MR 1663175
[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 1633669
[48] Li, Jiongsheng, Yin, Jianhua: Avariation of an extremal theorem due to Woodall. Southeast Asian Bull. Math. 25 (2001), 427-434. DOI 10.1007/s100120100006 | MR 1933948
[49] Li, Jiongsheng, Yin, Jianhua: On potentially $A\sb {r,s}$-graphic sequences. J. Math. Study 34 (2001), 1-4. MR 1828034
[50] Li, Jiongsheng, Yin, Jianhua: Extremal graph theory and degree sequences. Adv. Math. 33 (2004), 273-283. MR 2081838
[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 10.1007/s10114-005-0676-4 | MR 2245244
[52] Liu, Mingjing, Hu, Lili: On Potentially $K_5-Z_5$ graphic sequences. J. Zhangzhou Normal University 57 (2007), 20-24. MR 2563577
[53] Luo, Rong: On potentially $C_k$-graphic sequences. Ars Combinatoria 64 (2002), 301-318. MR 1914218
[54] Luo, Rong, Warner, Morgan: On potentially $K_k$-graphic sequences. Ars Combin. 75 (2005), 233-239. MR 2133225 | Zbl 1075.05021
[55] Mubayi, Dhruv: Graphic sequences that have a realization with large clique number. J. Graph Theory 34 (2000), 20-29. MR 1753064 | Zbl 0953.05013
[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 10.1016/j.endm.2007.01.018 | MR 2323956
[57] Xu, Zhenghua, Hu, Lili: Characterize the potentially $K_{1,4}+e$ graphical sequences. ZhangZhou Teachers College 55 (2007), 4-8. MR 2563577
[58] Yin, Jianhua: The smallest degree sum that yields potentially $K_{1,1,3}$-graphic sequences. J. HaiNan University 22 (2004), 200-204. MR 2229587
[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 2322209
[61] Yin, Jianhua, Chen, Gang: On potentially $K_{r_1,r_2,\cdots,r_m}$-graphic sequences. Util. Math. 72 (2007), 149-161. MR 2306237
[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 10.1016/j.disc.2007.11.075 | MR 2464911
[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 1915880 | Zbl 1099.05505
[64] Yin, Jianhua, Li, Jiongsheng: On the threshold in the Erdos-Jacobson-Lehel problem. Math. Appl. 15 (2002), 123-128. MR 1889152
[65] Yin, Jianhua, Li, Jiongsheng: An extremal problem on the potentially $K_{r,s}$-graphic sequences. Discrete Math. (2003), 260 295-305. MR 1948398
[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 10.1016/j.disc.2005.03.028 | MR 2171314
[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 10.1016/j.disc.2006.07.037 | MR 2292544
[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 10.1016/S0012-365X(03)00137-7 | MR 1997908
[69] Yin, Jianhua, Li, Jiongsheng, Chen, Guoliang: A variation of a classical Turn-type extremal problem. Eur. J. Comb. 25 (2004), 989-1002. DOI 10.1016/j.ejc.2003.12.011 | MR 2083451
[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 2119003
[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 2118998
[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 10.1007/s10255-006-0321-8 | MR 2229587 | Zbl 1106.05031
[73] Yin, Mengxiao, Yin, Jianhua: On potentially $H$-graphic sequences. Czech. Math. J. 57 (2007), 705-724. DOI 10.1007/s10587-007-0108-y | MR 2337625
Search
Partner of
