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

Chunhui Lai; Lili Hu

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

Access Full Article

top

Access to full text

Full (PDF)

Abstract

top

The set of all non-increasing nonnegative integer sequences

π =

(

d (v_{1}), d (v_{2}), \dots, d (v_{n})

) is denoted by

{NS}_{n}

. A sequence

π \in {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

MLA
BibTeX
RIS

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

Bollobás, B., Extremal Graph Theory, Academic Press, London (1978). (1978) MR0506522
Chen, Gang, Potentially $C_{6}$ -graphic sequences, J. Guangxi Univ. Nat. Sci. Ed. 28 (2003), 119-124. (2003) MR1997256
Chen, Gang, Characterize the potentially $K_{1, 2, 2}$ -graphic sequences, Journal of Qingdao University of Science and Technology 27 (2006), 86-88. (2006)
Chen, Gang, The smallest degree sum that yields potentially fan graphical sequences, J. Northwest Norm. Univ., Nat. Sci. 42 (2006), 27-30. (2006) Zbl1103.05302 MR2253937
Chen, Gang, An extremal problem on potentially $K_{r, s, t}$ -graphic sequences, J. YanTai University 19 (2006), 245-252. (2006) MR2260663
Chen, Gang, Potentially $K_{3, s} - k e$ graphical sequences, Guangxi Sciences 13 (2006), 164-171. (2006)
Chen, Gang, A note on potentially $K_{1, 1, t}$ -graphic sequences, Australasian J. Combin. 37 (2007), 21-26. (2007) Zbl1121.05034 MR2284364
Chen, Gang, Li, Xining, On potentially $K_{1, t} + e$ -graphic sequences, J. Zhangzhou Teach. Coll. 20 (2007), 5-7. (2007) Zbl1174.05339 MR2668610
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.05501 MR1987158
Chen, Gang, Yin, Jianhua, Fan, Yingmei, Potentially $_{k} C_{6}$ -graphic sequences, J. Guangxi Norm. Univ. Nat. Sci. 24 (2006), 26-29. (2006) MR2259980
Chen, Guantao, Ferrara, Michael, Gould, Ronald J., Schmitt, John R., Graphic sequences with a realization containing a complete multipartite subgraph, accepted by Discrete Mathematics, .
Erdös, P., Gallai, T., Graphs with given degrees of vertices, Math. Lapok 11 (1960), 264-274. (1960)
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
Eschen, Elaine M., Niu, Jianbing, On potentially $K_{4} - e$ -graphic sequences, Australasian J. Combin. 29 (2004), 59-65. (2004) Zbl1049.05027 MR2037333
Ferrara, Michael J., 10.1007/s00373-007-0737-9, Graphs and Combinatorics 23 (2007), 263-269. (2007) Zbl1123.05028 MR2320581 DOI10.1007/s00373-007-0737-9
Ferrara, M., Gould, R., Schmitt, J., Potentially $K_{s}^{t}$ -graphic degree sequences, submitted, .
Ferrara, M., Gould, R., Schmitt, J., Graphic sequences with a realization containing a friendship graph, Ars Combinatoria 85 (2007), 161-171. (2007) MR2359288
Ferrara, M., Jacobson, M., Schmitt, J., Siggers, M., Potentially $H$ -bigraphic sequences, submitted, .
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
Gupta, Gautam, Joshi, Puneet, Tripathi, Amitabha, 10.1007/s10587-007-0042-z, Czech. Math. J. 57 (2007), 49-52. (2007) Zbl1174.05023 MR2309947 DOI10.1007/s10587-007-0042-z
Hu, Lili, Lai, Chunhui, On potentially $K_{5} - C_{4}$ -graphic sequences, accepted by Ars Combinatoria, .
Hu, Lili, Lai, Chunhui, On potentially $K_{5} - Z_{4}$ -graphic sequences, submitted, .
Hu, Lili, Lai, Chunhui, On potentially $K_{5} - E_{3}$ -graphic sequences, accepted by Ars Combinatoria, .
Hu, Lili, Lai, Chunhui, On Potentially 3-regular graph graphic Sequences, accepted by Utilitas Mathematica, .
Hu, Lili, Lai, Chunhui, Wang, Ping, On potentially $K_{5} - H$ -graphic sequences, accepted by Czech. Math. J, .
Huang, Qin, On potentially $K_{m} - e$ -graphic sequences, J. ZhangZhou Teachers College 15 (2002), 26-28. (2002) MR1952471
Huang, Qin, On potentially $K_{5} - e$ -graphic sequences, J. XinJiang University 22 (2005), 276-284. (2005) MR2175912
Kleitman, D. J., Wang, D. L., 10.1016/0012-365X(73)90037-X, Discrete Math. 6 (1973), 79-88. (1973) MR0327559 DOI10.1016/0012-365X(73)90037-X
Lai, Chunhui, On potentially $C_{k}$ -graphic sequences, J. ZhangZhou Teachers College 11 (1997), 27-31. (1997)
Lai, Chunhui, A note on potentially $K_{4} - e$ graphical sequences, Australasian J. of Combinatorics 24 (2001), 123-127. (2001) Zbl0983.05025 MR1852813
Lai, Chunhui, Characterize the potentially $K_{4} - e$ graphical sequences, J. ZhangZhou Teachers College 15 (2002), 53-59. (2002) MR1709888
Lai, Chunhui, The Smallest Degree Sum that Yields Potentially $C_{k}$ -graphic Sequences, J. Combin. Math. Combin. Comput. 49 (2004), 57-64. (2004) MR2054962
Lai, Chunhui, An extremal problem on potentially $K_{p, 1, \dots, 1}$ -graphic sequences, J. Zhangzhou Teachers College 17 (2004), 11-13. (2004) MR2164060
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.05021 MR2164060
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.05016 MR2322201
Lai, Chunhui, An extremal problem on potentially $K_{m} - P_{k}$ -graphic sequences, accepted by International Journal of Pure and Applied Mathematics, .
Lai, Chunhui, The smallest degree sum that yields potentially $K_{r + 1} - Z$ -graphical Sequences, accepted by Ars Combinatoria, .
Lai, Chunhui, Hu, Lili, An extremal problem on potentially $K_{r + 1} - H$ -graphic sequences, accepted by Ars Combinatoria, .
Lai, Chunhui, Sun, Yuzhen, An extremal problem on potentially $K_{r + 1} - (k P_{2} \cup t K_{2})$ -graphic sequences, International Journal of Applied Mathematics & Statistics 14 (2009), 30-36. (2009) MR2524881
Lai, Chunhui, Yan, Guiying, On potentially $K_{r + 1} - U$ -graphical Sequences, accepted by Utilitas Mathematica, .
Li, Jiongsheng, Luo, Rong, Potentially $_{3} C_{l}$ -Graphic Sequences, J. Univ. Sci. Technol. China 29 (1999), 1-8. (1999) MR1707604
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.05043 MR1685466
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) MR1644418 DOI10.1002/(SICI)1097-0118(199810)29:2<63::AID-JGT2>3.0.CO;2-A
Li, Jiongsheng, Song, Zi-xia, On the potentially $P_{k}$ -graphic sequences, Discrete Math. 195 (1999), 255-262. (1999) MR1663863
Li, Jiongsheng, Song, Zi-xia, 10.1016/S0012-365X(99)00289-7, Discrete Math. 212 (2000), 223-231. (2000) MR1748652 DOI10.1016/S0012-365X(99)00289-7
Li, Jiongsheng, Song, Zi-xia, Luo, Rong, 10.1007/BF02879940, Science in China (Series A) 41 (1998), 510-520. (1998) MR1663175 DOI10.1007/BF02879940
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
Li, Jiongsheng, Yin, Jianhua, 10.1007/s100120100006, Southeast Asian Bull. Math. 25 (2001), 427-434. (2001) MR1933948 DOI10.1007/s100120100006
Li, Jiongsheng, Yin, Jianhua, On potentially $A_{r, s}$ -graphic sequences, J. Math. Study 34 (2001), 1-4. (2001) MR1828034
Li, Jiongsheng, Yin, Jianhua, Extremal graph theory and degree sequences, Adv. Math. 33 (2004), 273-283. (2004) MR2081838
Li, Jiong Sheng, Yin, Jianhua, 10.1007/s10114-005-0676-4, Acta Math. Sin. (Engl. Ser.) 22 (2006), 1133-1138. (2006) MR2245244 DOI10.1007/s10114-005-0676-4
Liu, Mingjing, Hu, Lili, On Potentially $K_{5} - Z_{5}$ graphic sequences, J. Zhangzhou Normal University 57 (2007), 20-24. (2007) MR2563577
Luo, Rong, On potentially $C_{k}$ -graphic sequences, Ars Combinatoria 64 (2002), 301-318. (2002) MR1914218
Luo, Rong, Warner, Morgan, On potentially $K_{k}$ -graphic sequences, Ars Combin. 75 (2005), 233-239. (2005) Zbl1075.05021 MR2133225
Mubayi, Dhruv, Graphic sequences that have a realization with large clique number, J. Graph Theory 34 (2000), 20-29. (2000) Zbl0953.05013 MR1753064
Schmitt, J. R., Ferrara, M., 10.1016/j.endm.2007.01.018, Electronic Notes in Discrete Mathematics 28 (2007), 131-135. (2007) MR2323956 DOI10.1016/j.endm.2007.01.018
Xu, Zhenghua, Hu, Lili, Characterize the potentially $K_{1, 4} + e$ graphical sequences, ZhangZhou Teachers College 55 (2007), 4-8. (2007) MR2563577
Yin, Jianhua, The smallest degree sum that yields potentially $K_{1, 1, 3}$ -graphic sequences, J. HaiNan University 22 (2004), 200-204. (2004) MR2229587
Yin, Jianhua, Some new conditions for a graphic sequence to have a realization with prescribed clique size, submitted, .
Yin, Jianhua, Chen, Gang, Chen, Guoliang, On potentially $_{k} C_{l}$ -graphic sequences, J. Combin. Math. Combin. Comput. 61 (2007), 141-148. (2007) MR2322209
Yin, Jianhua, Chen, Gang, On potentially $K_{r_{1}, r_{2}, \dots, r_{m}}$ -graphic sequences, Util. Math. 72 (2007), 149-161. (2007) MR2306237
Yin, Jianhua, Chen, Gang, Schmitt, John R., 10.1016/j.disc.2007.11.075, Discrete Mathematics 308 (2008), 6226-6232. (2008) MR2464911 DOI10.1016/j.disc.2007.11.075
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.05505 MR1915880
Yin, Jianhua, Li, Jiongsheng, On the threshold in the Erdos-Jacobson-Lehel problem, Math. Appl. 15 (2002), 123-128. (2002) MR1889152
Yin, Jianhua, Li, Jiongsheng, An extremal problem on the potentially $K_{r, s}$ -graphic sequences, Discrete Math. (2003), 260 295-305. (2003) MR1948398
Yin, Jianhua, Li, Jiongsheng, 10.1016/j.disc.2005.03.028, Discrete Math. 301 (2005), 218-227. (2005) MR2171314 DOI10.1016/j.disc.2005.03.028
Yin, Jianhua, Li, Jiongsheng, 10.1016/j.disc.2006.07.037, Discrete Mathematics 307 (2007), 1167-1177. (2007) MR2292544 DOI10.1016/j.disc.2006.07.037
Yin, Jianhua, Li, Jiongsheng, Chen, Guoliang, 10.1016/S0012-365X(03)00137-7, Discrete Mathematics 270 (2003), 319-327. (2003) MR1997908 DOI10.1016/S0012-365X(03)00137-7
Yin, Jianhua, Li, Jiongsheng, Chen, Guoliang, 10.1016/j.ejc.2003.12.011, Eur. J. Comb. 25 (2004), 989-1002. (2004) MR2083451 DOI10.1016/j.ejc.2003.12.011
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
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
Yin, Mengxiao, 10.1007/s10255-006-0321-8, Acta Math. Appl. Sin. Engl. Ser. 22 (2006), 451-456. (2006) Zbl1106.05031 MR2229587 DOI10.1007/s10255-006-0321-8
Yin, Mengxiao, Yin, Jianhua, 10.1007/s10587-007-0108-y, Czech. Math. J. 57 (2007), 705-724. (2007) MR2337625 DOI10.1007/s10587-007-0108-y

Citations in EuDML Documents

top

Jian Hua Yin, A Havel-Hakimi type procedure and a sufficient condition for a sequence to be potentially $S_{r, s}$ -graphic

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.

Language to use for this widget.

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

Number of notes per page

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.