| Title:
|
Potentially $K_m-G$-graphical sequences: A survey (English) |
| Author:
|
Lai, Chunhui |
| Author:
|
Hu, Lili |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
59 |
| Issue:
|
4 |
| Year:
|
2009 |
| Pages:
|
1059-1075 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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)$. (English) |
| Keyword:
|
graph |
| Keyword:
|
degree sequence |
| Keyword:
|
potentially $K_m-G$-graphic sequences |
| MSC:
|
05C07 |
| MSC:
|
05C35 |
| idZBL:
|
Zbl 1224.05105 |
| idMR:
|
MR2563577 |
| . |
| Date available:
|
2010-07-20T16:01:41Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/140536 |
| . |
| Reference:
|
[1] Bollobás, B.: Extremal Graph Theory.Academic Press, London (1978). MR 0506522 |
| Reference:
|
[2] Chen, Gang: Potentially $C\sb 6$-graphic sequences.J. Guangxi Univ. Nat. Sci. Ed. 28 (2003), 119-124. MR 1997256 |
| Reference:
|
[3] Chen, Gang: Characterize the potentially $K_{1,2,2}$-graphic sequences.Journal of Qingdao University of Science and Technology 27 (2006), 86-88. |
| Reference:
|
[4] Chen, Gang: The smallest degree sum that yields potentially fan graphical sequences.J. Northwest Norm. Univ., Nat. Sci. 42 (2006), 27-30. Zbl 1103.05302, MR 2253937 |
| Reference:
|
[5] Chen, Gang: An extremal problem on potentially $K_{r,s,t}$-graphic sequences.J. YanTai University 19 (2006), 245-252. MR 2260663 |
| Reference:
|
[6] Chen, Gang: Potentially $K_{3,s}-ke$ graphical sequences.Guangxi Sciences 13 (2006), 164-171. |
| Reference:
|
[7] Chen, Gang: A note on potentially $K_{1,1,t}$-graphic sequences.Australasian J. Combin. 37 (2007), 21-26. Zbl 1121.05034, MR 2284364 |
| Reference:
|
[8] Chen, Gang, Li, Xining: On potentially $K_{1,t}+e$-graphic sequences.J. Zhangzhou Teach. Coll. 20 (2007), 5-7. Zbl 1174.05339, MR 2668610 |
| Reference:
|
[9] Chen, Gang, Yin, Jianhua: The smallest degree sum that yields potentially $W_5$-graphic sequences.J. XuZhou Normal University 21 (2003), 5-7. Zbl 1036.05501, MR 1987158 |
| Reference:
|
[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 |
| Reference:
|
[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.. |
| Reference:
|
[12] Erdös, P., Gallai, T.: Graphs with given degrees of vertices.Math. Lapok 11 (1960), 264-274. |
| Reference:
|
[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 |
| Reference:
|
[14] Eschen, Elaine M., Niu, Jianbing: On potentially $K_4-e$-graphic sequences.Australasian J. Combin. 29 (2004), 59-65. Zbl 1049.05027, MR 2037333 |
| Reference:
|
[15] Ferrara, Michael J.: Graphic sequences with a realization containing a union of cliques.Graphs and Combinatorics 23 (2007), 263-269. Zbl 1123.05028, MR 2320581, 10.1007/s00373-007-0737-9 |
| Reference:
|
[16] Ferrara, M., Gould, R., Schmitt, J.: Potentially $K_s^t$-graphic degree sequences, submitted.. |
| Reference:
|
[17] Ferrara, M., Gould, R., Schmitt, J.: Graphic sequences with a realization containing a friendship graph.Ars Combinatoria 85 (2007), 161-171. MR 2359288 |
| Reference:
|
[18] Ferrara, M., Jacobson, M., Schmitt, J., Siggers, M.: Potentially $H$-bigraphic sequences, submitted.. |
| Reference:
|
[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 |
| Reference:
|
[20] Gupta, Gautam, Joshi, Puneet, Tripathi, Amitabha: Graphic sequences of trees and a problem of Frobenius.Czech. Math. J. 57 (2007), 49-52. Zbl 1174.05023, MR 2309947, 10.1007/s10587-007-0042-z |
| Reference:
|
[21] Hu, Lili, Lai, Chunhui: On potentially $K_5-C_4$-graphic sequences, accepted by Ars Combinatoria.. |
| Reference:
|
[22] Hu, Lili, Lai, Chunhui: On potentially $K_5-Z_4$-graphic sequences, submitted.. |
| Reference:
|
[23] Hu, Lili, Lai, Chunhui: On potentially $K_5-E_3$-graphic sequences, accepted by Ars Combinatoria.. |
| Reference:
|
[24] Hu, Lili, Lai, Chunhui: On Potentially 3-regular graph graphic Sequences, accepted by Utilitas Mathematica.. |
| Reference:
|
[25] Hu, Lili, Lai, Chunhui, Wang, Ping: On potentially $K_5-H$-graphic sequences, accepted by Czech. Math. J.. |
| Reference:
|
[26] Huang, Qin: On potentially $K_m-e$-graphic sequences.J. ZhangZhou Teachers College 15 (2002), 26-28. MR 1952471 |
| Reference:
|
[27] Huang, Qin: On potentially $K_5-e$-graphic sequences.J. XinJiang University 22 (2005), 276-284. MR 2175912 |
| Reference:
|
[28] Kleitman, D. J., Wang, D. L.: Algorithm for constructing graphs and digraphs with given valences and factors.Discrete Math. 6 (1973), 79-88. MR 0327559, 10.1016/0012-365X(73)90037-X |
| Reference:
|
[29] Lai, Chunhui: On potentially $C_k$-graphic sequences.J. ZhangZhou Teachers College 11 (1997), 27-31. |
| Reference:
|
[30] Lai, Chunhui: A note on potentially $K_4-e$ graphical sequences.Australasian J. of Combinatorics 24 (2001), 123-127. Zbl 0983.05025, MR 1852813 |
| Reference:
|
[31] Lai, Chunhui: Characterize the potentially $K_4-e$ graphical sequences.J. ZhangZhou Teachers College 15 (2002), 53-59. MR 1709888 |
| Reference:
|
[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 |
| Reference:
|
[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 |
| Reference:
|
[34] Lai, Chunhui: An extremal problem on potentially $K_{p,1,1}$-graphic sequences.Discrete Mathematics and Theoretical Computer Science 7 (2005), 75-80. Zbl 1153.05021, MR 2164060 |
| Reference:
|
[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. Zbl 1139.05016, MR 2322201 |
| Reference:
|
[36] Lai, Chunhui: An extremal problem on potentially $K_m-P_k$-graphic sequences, accepted by International Journal of Pure and Applied Mathematics.. |
| Reference:
|
[37] Lai, Chunhui: The smallest degree sum that yields potentially $K_{r+1}-Z$-graphical Sequences, accepted by Ars Combinatoria.. |
| Reference:
|
[38] Lai, Chunhui, Hu, Lili: An extremal problem on potentially $K_{r+1}-H$-graphic sequences, accepted by Ars Combinatoria.. |
| Reference:
|
[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 |
| Reference:
|
[40] Lai, Chunhui, Yan, Guiying: On potentially $K_{r+1}-U$-graphical Sequences, accepted by Utilitas Mathematica.. |
| Reference:
|
[41] Li, Jiongsheng, Luo, Rong: Potentially $_3C_l$-Graphic Sequences.J. Univ. Sci. Technol. China 29 (1999), 1-8. MR 1707604 |
| Reference:
|
[42] Li, Jiongsheng, Luo, Rong, Liu, Yunkai: An extremal problem on potentially $_3C_l$-graphic sequences.J. Math. Study 31 (1998), 362-369. Zbl 0920.05043, MR 1685466 |
| Reference:
|
[43] Li, Jiongsheng, Song, Zi-xia: The smallest degree sum that yields potentially $P_k$-graphical sequences.J. Graph Theory 29 (1998), 63-72. MR 1644418, 10.1002/(SICI)1097-0118(199810)29:2<63::AID-JGT2>3.0.CO;2-A |
| Reference:
|
[44] Li, Jiongsheng, Song, Zi-xia: On the potentially $P_k$-graphic sequences.Discrete Math. 195 (1999), 255-262. MR 1663863 |
| Reference:
|
[45] Li, Jiongsheng, Song, Zi-xia: An extremal problem on the potentially $P_k$-graphic sequences.Discrete Math. 212 (2000), 223-231. MR 1748652, 10.1016/S0012-365X(99)00289-7 |
| Reference:
|
[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. MR 1663175, 10.1007/BF02879940 |
| Reference:
|
[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 |
| Reference:
|
[48] Li, Jiongsheng, Yin, Jianhua: Avariation of an extremal theorem due to Woodall.Southeast Asian Bull. Math. 25 (2001), 427-434. MR 1933948, 10.1007/s100120100006 |
| Reference:
|
[49] Li, Jiongsheng, Yin, Jianhua: On potentially $A\sb {r,s}$-graphic sequences.J. Math. Study 34 (2001), 1-4. MR 1828034 |
| Reference:
|
[50] Li, Jiongsheng, Yin, Jianhua: Extremal graph theory and degree sequences.Adv. Math. 33 (2004), 273-283. MR 2081838 |
| Reference:
|
[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. MR 2245244, 10.1007/s10114-005-0676-4 |
| Reference:
|
[52] Liu, Mingjing, Hu, Lili: On Potentially $K_5-Z_5$ graphic sequences.J. Zhangzhou Normal University 57 (2007), 20-24. MR 2563577 |
| Reference:
|
[53] Luo, Rong: On potentially $C_k$-graphic sequences.Ars Combinatoria 64 (2002), 301-318. MR 1914218 |
| Reference:
|
[54] Luo, Rong, Warner, Morgan: On potentially $K_k$-graphic sequences.Ars Combin. 75 (2005), 233-239. Zbl 1075.05021, MR 2133225 |
| Reference:
|
[55] Mubayi, Dhruv: Graphic sequences that have a realization with large clique number.J. Graph Theory 34 (2000), 20-29. Zbl 0953.05013, MR 1753064 |
| Reference:
|
[56] Schmitt, J. R., Ferrara, M.: An Erdös-Stone Type Conjecture for Graphic Sequences.Electronic Notes in Discrete Mathematics 28 (2007), 131-135. MR 2323956, 10.1016/j.endm.2007.01.018 |
| Reference:
|
[57] Xu, Zhenghua, Hu, Lili: Characterize the potentially $K_{1,4}+e$ graphical sequences.ZhangZhou Teachers College 55 (2007), 4-8. MR 2563577 |
| Reference:
|
[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 |
| Reference:
|
[59] Yin, Jianhua: Some new conditions for a graphic sequence to have a realization with prescribed clique size, submitted.. |
| Reference:
|
[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 |
| Reference:
|
[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 |
| Reference:
|
[62] Yin, Jianhua, Chen, Gang, Schmitt, John R.: Graphic Sequences with a realization containing a generalized Friendship Graph.Discrete Mathematics 308 (2008), 6226-6232. MR 2464911, 10.1016/j.disc.2007.11.075 |
| Reference:
|
[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. Zbl 1099.05505, MR 1915880 |
| Reference:
|
[64] Yin, Jianhua, Li, Jiongsheng: On the threshold in the Erdos-Jacobson-Lehel problem.Math. Appl. 15 (2002), 123-128. MR 1889152 |
| Reference:
|
[65] Yin, Jianhua, Li, Jiongsheng: An extremal problem on the potentially $K_{r,s}$-graphic sequences.Discrete Math. (2003), 260 295-305. MR 1948398 |
| Reference:
|
[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. MR 2171314, 10.1016/j.disc.2005.03.028 |
| Reference:
|
[67] Yin, Jianhua, Li, Jiongsheng: Potentially $K_{r_1,r_2,\cdots,r_l,r,s}$-graphic sequences.Discrete Mathematics 307 (2007), 1167-1177. MR 2292544, 10.1016/j.disc.2006.07.037 |
| Reference:
|
[68] Yin, Jianhua, Li, Jiongsheng, Chen, Guoliang: The smallest degree sum that yields potentially $_3C_l$-graphic sequences.Discrete Mathematics 270 (2003), 319-327. MR 1997908, 10.1016/S0012-365X(03)00137-7 |
| Reference:
|
[69] Yin, Jianhua, Li, Jiongsheng, Chen, Guoliang: A variation of a classical Turn-type extremal problem.Eur. J. Comb. 25 (2004), 989-1002. MR 2083451, 10.1016/j.ejc.2003.12.011 |
| Reference:
|
[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 |
| Reference:
|
[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 |
| Reference:
|
[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. Zbl 1106.05031, MR 2229587, 10.1007/s10255-006-0321-8 |
| Reference:
|
[73] Yin, Mengxiao, Yin, Jianhua: On potentially $H$-graphic sequences.Czech. Math. J. 57 (2007), 705-724. MR 2337625, 10.1007/s10587-007-0108-y |
| . |
