Geodesic
On potentially $K_5-H$-graphic sequences
Czechoslovak Mathematical Journal, Tome 59 (2009) no. 1, pp. 173-182 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

Let $K_m-H$ be the graph obtained from $K_m$ by removing the edges set $E(H)$ of $H$ where $H$ is a subgraph of $K_m$. In this paper, we characterize the potentially $K_5-P_4$ and $K_5-Y_4$-graphic sequences where $Y_4$ is a tree on 5 vertices and 3 leaves.
Let $K_m-H$ be the graph obtained from $K_m$ by removing the edges set $E(H)$ of $H$ where $H$ is a subgraph of $K_m$. In this paper, we characterize the potentially $K_5-P_4$ and $K_5-Y_4$-graphic sequences where $Y_4$ is a tree on 5 vertices and 3 leaves.
Classification : 05C07, 05C35
Keywords: graph; degree sequence; potentially $K_5-H$-graphic sequence 
@article{CMJ_2009_59_1_a11,
     author = {Hu, Lili and Lai, Chunhui and Wang, Ping},
     title = {On potentially $K_5-H$-graphic sequences},
     journal = {Czechoslovak Mathematical Journal},
     pages = {173--182},
     year = {2009},
     volume = {59},
     number = {1},
     mrnumber = {2486623},
     zbl = {1224.05104},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMJ_2009_59_1_a11/}
}
TY  - JOUR
AU  - Hu, Lili
AU  - Lai, Chunhui
AU  - Wang, Ping
TI  - On potentially $K_5-H$-graphic sequences
JO  - Czechoslovak Mathematical Journal
PY  - 2009
SP  - 173
EP  - 182
VL  - 59
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/CMJ_2009_59_1_a11/
LA  - en
ID  - CMJ_2009_59_1_a11
ER  - 
%0 Journal Article
%A Hu, Lili
%A Lai, Chunhui
%A Wang, Ping
%T On potentially $K_5-H$-graphic sequences
%J Czechoslovak Mathematical Journal
%D 2009
%P 173-182
%V 59
%N 1
%U http://geodesic.mathdoc.fr/item/CMJ_2009_59_1_a11/
%G en
%F CMJ_2009_59_1_a11
Hu, Lili; Lai, Chunhui; Wang, Ping. On potentially $K_5-H$-graphic sequences. Czechoslovak Mathematical Journal, Tome 59 (2009) no. 1, pp. 173-182. http://geodesic.mathdoc.fr/item/CMJ_2009_59_1_a11/

[1] Bondy, J. A., Murty, U. S. R.: Graph Theory with Applications. Macmillan Press (1976). | MR

[2] Erdös, P., Jacobson, M. S., Lehel, J.: Graphs realizing the same degree sequences and their respective clique numbers. In: Graph Theory, Combinatorics and Application, Vol. 1 Y. Alavi et al. John Wiley and Sons New York (1991), 439-449. | MR

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

[4] Gupta, G., Joshi, P., Tripathi, A.: Graphic sequences of trees and a problem of Frobenius. Czech. Math. J. 57 (2007), 49-52. | DOI | MR | Zbl

[5] Ferrara, M., Schmitt, R. Gould,J.: Potentially $K_s^t$-graphic degree sequences. Submitted.

[6] Ferrara, M., Gould, R., Schmitt, J.: Graphic sequences with a realization containing a friendship graph. Ars Comb Accepted.

[7] Hu, Lili, Lai, Chunhui: On potentially $K_5-C_4$-graphic sequences. Ars Comb Accepted.

[8] Hu, Lili, Lai, Chunhui: On potentially $K_5-Z_4$-graphic sequences. Submitted.

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

[10] Lai, Chunhui: A note on potentially $K_4-e$ graphical sequences. Australas J. Comb. 24 (2001), 123-127. | MR | Zbl

[11] Lai, Chunhui: An extremal problem on potentially $K_m-P_k$-graphic sequences. Int. J. Pure Appl. Math Accepted.

[12] Lai, Chunhui: An extremal problem on potentially $K_m-C_4$-graphic sequences. J. Comb. Math. Comb. Comput. 61 (2007), 59-63. | MR | Zbl

[13] Lai, Chunhui: An extremal problem on potentially $K_{p,1,1}$-graphic sequences. Discret. Math. Theor. Comput. Sci. 7 (2005), 75-80. | MR | Zbl

[14] Lai, Chunhui, Hu, Lili: An extremal problem on potentially $K_{r+1}-H$-graphic sequences. Ars Comb Accepted.

[15] Lai, Chunhui: The smallest degree sum that yields potentially $K_{r+1}-Z$-graphical sequences. Ars Comb Accepted.

[16] Li, Jiong-Sheng, Song, Zi-Xia: An extremal problem on the potentially $P_k$-graphic sequences. In: Proc. International Symposium on Combinatorics and Applications, June 28-30, 1996 W. Y. C. Chen et. al. Nankai University Tianjin (1996), 269-276.

[17] Li, Jiong-Sheng, Song, Zi-Xia: The smallest degree sum that yields potentially $P_k$-graphical sequences. J. Graph Theory 29 (1998), 63-72. | DOI | MR | Zbl

[18] Li, Jiong-sheng, Song, Zi-Xia, Luo, Rong: The Erdös-Jacobson-Lehel conjecture on potentially $P_k$-graphic sequence is true. Sci. China (Ser. A) 41 (1998), 510-520. | DOI | MR

[19] Li, Jiong-sheng, Yin, Jianhua: A variation of an extremal theorem due to Woodall. Southeast Asian Bull. Math. 25 (2001), 427-434. | DOI | MR

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

[21] Luo, R., Warner, M.: On potentially $K_k$-graphic sequences. Ars Combin. 75 (2005), 233-239. | MR | Zbl

[22] Eschen, E. M., Niu, J.: On potentially $K_4-e$-graphic sequences. Australas J. Comb. 29 (2004), 59-65. | MR | Zbl

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

[24] Yin, J.-H., Li, J.-S., Mao, R.: An extremal problem on the potentially $K_{r+1}-e$-graphic sequences. Ars Comb. 74 (2005), 151-159. | MR

[25] Yin, J.-H., Chen, G.: On potentially $K_{r_1,r_2,\cdots,r_m}$-graphic sequences. Util. Math. 72 (2007), 149-161. | MR

[26] Yin, M.: 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 | MR | Zbl