Geodesic
On potentially $H$-graphic sequences
Czechoslovak Mathematical Journal, Tome 57 (2007) no. 2, pp. 705-724 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

For given a graph $H$, a graphic sequence $\pi =(d_1,d_2,\ldots ,d_n)$ is said to be potentially $H$-graphic if there is a realization of $\pi $ containing $H$ as a subgraph. In this paper, we characterize the potentially $(K_5-e)$-positive graphic sequences and give two simple necessary and sufficient conditions for a positive graphic sequence $\pi $ to be potentially $K_5$-graphic, where $K_r$ is a complete graph on $r$ vertices and $K_r-e$ is a graph obtained from $K_r$ by deleting one edge. Moreover, we also give a simple necessary and sufficient condition for a positive graphic sequence $\pi $ to be potentially $K_6$-graphic.
For given a graph $H$, a graphic sequence $\pi =(d_1,d_2,\ldots ,d_n)$ is said to be potentially $H$-graphic if there is a realization of $\pi $ containing $H$ as a subgraph. In this paper, we characterize the potentially $(K_5-e)$-positive graphic sequences and give two simple necessary and sufficient conditions for a positive graphic sequence $\pi $ to be potentially $K_5$-graphic, where $K_r$ is a complete graph on $r$ vertices and $K_r-e$ is a graph obtained from $K_r$ by deleting one edge. Moreover, we also give a simple necessary and sufficient condition for a positive graphic sequence $\pi $ to be potentially $K_6$-graphic.
Classification : 05C07
Keywords: graph; degree sequence; potentially $H$-graphic sequence 
@article{CMJ_2007_57_2_a13,
     author = {Yin, Meng-Xiao and Yin, Jian-Hua},
     title = {On potentially $H$-graphic sequences},
     journal = {Czechoslovak Mathematical Journal},
     pages = {705--724},
     year = {2007},
     volume = {57},
     number = {2},
     mrnumber = {2337625},
     zbl = {1174.05024},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_2007_57_2_a13/}
}
TY  - JOUR
AU  - Yin, Meng-Xiao
AU  - Yin, Jian-Hua
TI  - On potentially $H$-graphic sequences
JO  - Czechoslovak Mathematical Journal
PY  - 2007
SP  - 705
EP  - 724
VL  - 57
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/CMJ_2007_57_2_a13/
LA  - en
ID  - CMJ_2007_57_2_a13
ER  - 
%0 Journal Article
%A Yin, Meng-Xiao
%A Yin, Jian-Hua
%T On potentially $H$-graphic sequences
%J Czechoslovak Mathematical Journal
%D 2007
%P 705-724
%V 57
%N 2
%U http://geodesic.mathdoc.fr/item/CMJ_2007_57_2_a13/
%G en
%F CMJ_2007_57_2_a13
Yin, Meng-Xiao; Yin, Jian-Hua. On potentially $H$-graphic sequences. Czechoslovak Mathematical Journal, Tome 57 (2007) no. 2, pp. 705-724. http://geodesic.mathdoc.fr/item/CMJ_2007_57_2_a13/

[1] P. Erdős, M. S. Jacobson and J. Lehel: Graphs realizing the same degree sequences and their respective clique numbers, in: Y. Alavi et al., (Eds.). Graph Theory, Combinatorics and Applications, Vol. 1, John Wiley & Sons, New York, 1991, pp. 439–449. | MR

[2] Elaine Eschen and J. B. Niu: On potentially $K_4-e$-graphic. Australasian J. Combinatorics 29 (2004), 59–65. | MR

[3] R. J. Gould, M. S. Jacobson and J. Lehel: Potentially $G$-graphical degree sequences, in: Y. Alavi et al., (Eds.). Combinatorics, Graph Theory, and Algorithms, Vol. 1, New Issues Press, Kalamazoo Michigan, 1999, pp. 451–460. | MR

[4] A. E. Kézdy and J. Lehel: Degree sequences of graphs with prescribed clique size, in: Y. Alavi et al., (Eds.). Combinatorics, Graph Theory, and Algorithms, Vol. 2, New Issues Press, Kalamazoo Michigan, 1999, pp. 535–544. | MR

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

[6] J. S. Li and Z. X. Song: An extremal problem on the potentially $P_k$-graphic sequences. Discrete Math. 212 (2000), 223–231. | DOI | MR

[7] J. S. Li and Z. X. Song: The smallest degree sum that yields potentially $P_k$-graphic sequences. J. Graph Theory 29 (1998), 63–72. | DOI | MR

[8] J. S. Li, Z. X. Song and R. Luo: The Erdős-Jacobson-Lehel conjecture on potentially $P_k$-graphic sequences is true. Science in China, Ser. A 41 (1998), 510–520. | DOI | MR

[9] J. S. Li and J. H. Yin: A variation of an extremal theorem due to Woodall. Southeast Asian Bulletin of Mathematics 25 (2001), 427–434. | DOI | MR

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

[11] R. Luo and Morgan Warner: On potentially $K_k$-graphic sequences. Ars Combinatoria 75 (2005), 233–239. | MR

[12] A. R. Rao: The clique number of a graph with given degree sequence. Proc. Symposium on Graph Theory, A. R. Rao ed., MacMillan and Co. India Ltd., I.S.I. Lecture Notes Series 4 (1979), 251–267.

[13] A. R. Rao: An Erdős-Gallai type result on the clique number of a realization of a degree sequence, unpublished.

[14] J. H. Yin and J. S. Li: An extremal problem on potentially $K_{r,s}$-graphic sequences. Discrete Math. 260 (2003), 295–305. | DOI | MR

[15] J. H. Yin and J. S. Li: Two sufficient conditions for a graphic sequence to have a realization with prescribed clique size. Discrete Math. 301 (2005), 218–227. | DOI | MR