Potentially K m - G -graphical sequences: A survey

Chunhui Lai; Lili Hu

Czechoslovak Mathematical Journal (2009)

  • Volume: 59, Issue: 4, page 1059-1075
  • ISSN: 0011-4642

Abstract

top
The set of all non-increasing nonnegative integer sequences π = ( d ( v 1 ) , d ( v 2 ) , ⋯ , d ( v n ) ) is denoted by NS n . A sequence π ∈ 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 π . The set of all graphic sequences in NS n is denoted by GS n . A graphical sequence π is potentially H -graphical if there is a realization of π containing H as a subgraph, while π is forcibly H -graphical if every realization of π 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 σ ( H , n ) .

How to cite

top

Lai, Chunhui, and Hu, Lili. "Potentially $K_m-G$-graphical sequences: A survey." Czechoslovak Mathematical Journal 59.4 (2009): 1059-1075. <http://eudml.org/doc/37977>.

@article{Lai2009,
abstract = {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)$.},
author = {Lai, Chunhui, Hu, Lili},
journal = {Czechoslovak Mathematical Journal},
keywords = {graph; degree sequence; potentially $K_m-G$-graphic sequences; graph; degree sequence; potentially -graphic sequence},
language = {eng},
number = {4},
pages = {1059-1075},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Potentially $K_m-G$-graphical sequences: A survey},
url = {http://eudml.org/doc/37977},
volume = {59},
year = {2009},
}

TY - JOUR
AU - Lai, Chunhui
AU - Hu, Lili
TI - Potentially $K_m-G$-graphical sequences: A survey
JO - Czechoslovak Mathematical Journal
PY - 2009
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 59
IS - 4
SP - 1059
EP - 1075
AB - 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)$.
LA - eng
KW - graph; degree sequence; potentially $K_m-G$-graphic sequences; graph; degree sequence; potentially -graphic sequence
UR - http://eudml.org/doc/37977
ER -

References

top
  1. Bollobás, B., Extremal Graph Theory, Academic Press, London (1978). (1978) MR0506522
  2. Chen, Gang, Potentially C 6 -graphic sequences, J. Guangxi Univ. Nat. Sci. Ed. 28 (2003), 119-124. (2003) MR1997256
  3. Chen, Gang, Characterize the potentially K 1 , 2 , 2 -graphic sequences, Journal of Qingdao University of Science and Technology 27 (2006), 86-88. (2006) 
  4. Chen, Gang, The smallest degree sum that yields potentially fan graphical sequences, J. Northwest Norm. Univ., Nat. Sci. 42 (2006), 27-30. (2006) Zbl1103.05302MR2253937
  5. Chen, Gang, An extremal problem on potentially K r , s , t -graphic sequences, J. YanTai University 19 (2006), 245-252. (2006) MR2260663
  6. Chen, Gang, Potentially K 3 , s - k e graphical sequences, Guangxi Sciences 13 (2006), 164-171. (2006) 
  7. Chen, Gang, A note on potentially K 1 , 1 , t -graphic sequences, Australasian J. Combin. 37 (2007), 21-26. (2007) Zbl1121.05034MR2284364
  8. Chen, Gang, Li, Xining, On potentially K 1 , t + e -graphic sequences, J. Zhangzhou Teach. Coll. 20 (2007), 5-7. (2007) Zbl1174.05339MR2668610
  9. Chen, Gang, Yin, Jianhua, The smallest degree sum that yields potentially W 5 -graphic sequences, J. XuZhou Normal University 21 (2003), 5-7. (2003) Zbl1036.05501MR1987158
  10. Chen, Gang, Yin, Jianhua, Fan, Yingmei, Potentially k C 6 -graphic sequences, J. Guangxi Norm. Univ. Nat. Sci. 24 (2006), 26-29. (2006) MR2259980
  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. (1960) 
  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. (1991) MR1170797
  14. Eschen, Elaine M., Niu, Jianbing, On potentially K 4 - e -graphic sequences, Australasian J. Combin. 29 (2004), 59-65. (2004) Zbl1049.05027MR2037333
  15. Ferrara, Michael J., 10.1007/s00373-007-0737-9, Graphs and Combinatorics 23 (2007), 263-269. (2007) Zbl1123.05028MR2320581DOI10.1007/s00373-007-0737-9
  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. (2007) MR2359288
  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. MR1985076
  20. Gupta, Gautam, Joshi, Puneet, Tripathi, Amitabha, 10.1007/s10587-007-0042-z, Czech. Math. J. 57 (2007), 49-52. (2007) Zbl1174.05023MR2309947DOI10.1007/s10587-007-0042-z
  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. (2002) MR1952471
  27. Huang, Qin, On potentially K 5 - e -graphic sequences, J. XinJiang University 22 (2005), 276-284. (2005) MR2175912
  28. Kleitman, D. J., Wang, D. L., 10.1016/0012-365X(73)90037-X, Discrete Math. 6 (1973), 79-88. (1973) MR0327559DOI10.1016/0012-365X(73)90037-X
  29. Lai, Chunhui, On potentially C k -graphic sequences, J. ZhangZhou Teachers College 11 (1997), 27-31. (1997) 
  30. Lai, Chunhui, A note on potentially K 4 - e graphical sequences, Australasian J. of Combinatorics 24 (2001), 123-127. (2001) Zbl0983.05025MR1852813
  31. Lai, Chunhui, Characterize the potentially K 4 - e graphical sequences, J. ZhangZhou Teachers College 15 (2002), 53-59. (2002) MR1709888
  32. Lai, Chunhui, The Smallest Degree Sum that Yields Potentially C k -graphic Sequences, J. Combin. Math. Combin. Comput. 49 (2004), 57-64. (2004) MR2054962
  33. Lai, Chunhui, An extremal problem on potentially K p , 1 , ⋯ , 1 -graphic sequences, J. Zhangzhou Teachers College 17 (2004), 11-13. (2004) MR2164060
  34. Lai, Chunhui, An extremal problem on potentially K p , 1 , 1 -graphic sequences, Discrete Mathematics and Theoretical Computer Science 7 (2005), 75-80. (2005) Zbl1153.05021MR2164060
  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. (2007) Zbl1139.05016MR2322201
  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 - ( k P 2 ∪ t K 2 ) -graphic sequences, International Journal of Applied Mathematics & Statistics 14 (2009), 30-36. (2009) MR2524881
  40. Lai, Chunhui, Yan, Guiying, On potentially K r + 1 - U -graphical Sequences, accepted by Utilitas Mathematica, . 
  41. Li, Jiongsheng, Luo, Rong, Potentially 3 C l -Graphic Sequences, J. Univ. Sci. Technol. China 29 (1999), 1-8. (1999) MR1707604
  42. Li, Jiongsheng, Luo, Rong, Liu, Yunkai, An extremal problem on potentially 3 C l -graphic sequences, J. Math. Study 31 (1998), 362-369. (1998) Zbl0920.05043MR1685466
  43. Li, Jiongsheng, Song, Zi-xia, 10.1002/(SICI)1097-0118(199810)29:2<63::AID-JGT2>3.0.CO;2-A, J. Graph Theory 29 (1998), 63-72. (1998) MR1644418DOI10.1002/(SICI)1097-0118(199810)29:2<63::AID-JGT2>3.0.CO;2-A
  44. Li, Jiongsheng, Song, Zi-xia, On the potentially P k -graphic sequences, Discrete Math. 195 (1999), 255-262. (1999) MR1663863
  45. Li, Jiongsheng, Song, Zi-xia, 10.1016/S0012-365X(99)00289-7, Discrete Math. 212 (2000), 223-231. (2000) MR1748652DOI10.1016/S0012-365X(99)00289-7
  46. Li, Jiongsheng, Song, Zi-xia, Luo, Rong, 10.1007/BF02879940, Science in China (Series A) 41 (1998), 510-520. (1998) MR1663175DOI10.1007/BF02879940
  47. Li, Jiongsheng, Song, Zi-xia, Wang, Ping, The Erdos-Jacobson-Lehel conjecture about potentially P k -graphic sequences, J. China Univ. Sci. Tech. 28 (1998), 1-9. (1998) MR1633669
  48. Li, Jiongsheng, Yin, Jianhua, 10.1007/s100120100006, Southeast Asian Bull. Math. 25 (2001), 427-434. (2001) MR1933948DOI10.1007/s100120100006
  49. Li, Jiongsheng, Yin, Jianhua, On potentially A r , s -graphic sequences, J. Math. Study 34 (2001), 1-4. (2001) MR1828034
  50. Li, Jiongsheng, Yin, Jianhua, Extremal graph theory and degree sequences, Adv. Math. 33 (2004), 273-283. (2004) MR2081838
  51. Li, Jiong Sheng, Yin, Jianhua, 10.1007/s10114-005-0676-4, Acta Math. Sin. (Engl. Ser.) 22 (2006), 1133-1138. (2006) MR2245244DOI10.1007/s10114-005-0676-4
  52. Liu, Mingjing, Hu, Lili, On Potentially K 5 - Z 5 graphic sequences, J. Zhangzhou Normal University 57 (2007), 20-24. (2007) MR2563577
  53. Luo, Rong, On potentially C k -graphic sequences, Ars Combinatoria 64 (2002), 301-318. (2002) MR1914218
  54. Luo, Rong, Warner, Morgan, On potentially K k -graphic sequences, Ars Combin. 75 (2005), 233-239. (2005) Zbl1075.05021MR2133225
  55. Mubayi, Dhruv, Graphic sequences that have a realization with large clique number, J. Graph Theory 34 (2000), 20-29. (2000) Zbl0953.05013MR1753064
  56. Schmitt, J. R., Ferrara, M., 10.1016/j.endm.2007.01.018, Electronic Notes in Discrete Mathematics 28 (2007), 131-135. (2007) MR2323956DOI10.1016/j.endm.2007.01.018
  57. Xu, Zhenghua, Hu, Lili, Characterize the potentially K 1 , 4 + e graphical sequences, ZhangZhou Teachers College 55 (2007), 4-8. (2007) MR2563577
  58. Yin, Jianhua, The smallest degree sum that yields potentially K 1 , 1 , 3 -graphic sequences, J. HaiNan University 22 (2004), 200-204. (2004) MR2229587
  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 k C l -graphic sequences, J. Combin. Math. Combin. Comput. 61 (2007), 141-148. (2007) MR2322209
  61. Yin, Jianhua, Chen, Gang, On potentially K r 1 , r 2 , ⋯ , r m -graphic sequences, Util. Math. 72 (2007), 149-161. (2007) MR2306237
  62. Yin, Jianhua, Chen, Gang, Schmitt, John R., 10.1016/j.disc.2007.11.075, Discrete Mathematics 308 (2008), 6226-6232. (2008) MR2464911DOI10.1016/j.disc.2007.11.075
  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. (2002) Zbl1099.05505MR1915880
  64. Yin, Jianhua, Li, Jiongsheng, On the threshold in the Erdos-Jacobson-Lehel problem, Math. Appl. 15 (2002), 123-128. (2002) MR1889152
  65. Yin, Jianhua, Li, Jiongsheng, An extremal problem on the potentially K r , s -graphic sequences, Discrete Math. (2003), 260 295-305. (2003) MR1948398
  66. Yin, Jianhua, Li, Jiongsheng, 10.1016/j.disc.2005.03.028, Discrete Math. 301 (2005), 218-227. (2005) MR2171314DOI10.1016/j.disc.2005.03.028
  67. Yin, Jianhua, Li, Jiongsheng, 10.1016/j.disc.2006.07.037, Discrete Mathematics 307 (2007), 1167-1177. (2007) MR2292544DOI10.1016/j.disc.2006.07.037
  68. Yin, Jianhua, Li, Jiongsheng, Chen, Guoliang, 10.1016/S0012-365X(03)00137-7, Discrete Mathematics 270 (2003), 319-327. (2003) MR1997908DOI10.1016/S0012-365X(03)00137-7
  69. Yin, Jianhua, Li, Jiongsheng, Chen, Guoliang, 10.1016/j.ejc.2003.12.011, Eur. J. Comb. 25 (2004), 989-1002. (2004) MR2083451DOI10.1016/j.ejc.2003.12.011
  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. (2005) MR2119003
  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. (2005) MR2118998
  72. Yin, Mengxiao, 10.1007/s10255-006-0321-8, Acta Math. Appl. Sin. Engl. Ser. 22 (2006), 451-456. (2006) Zbl1106.05031MR2229587DOI10.1007/s10255-006-0321-8
  73. Yin, Mengxiao, Yin, Jianhua, 10.1007/s10587-007-0108-y, Czech. Math. J. 57 (2007), 705-724. (2007) MR2337625DOI10.1007/s10587-007-0108-y

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.