On potentially K 5 - H -graphic sequences

Lili Hu; Chunhui Lai; Ping Wang

Czechoslovak Mathematical Journal (2009)

  • Volume: 59, Issue: 1, page 173-182
  • ISSN: 0011-4642

Abstract

top
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.

How to cite

top

Hu, Lili, Lai, Chunhui, and Wang, Ping. "On potentially $K_5-H$-graphic sequences." Czechoslovak Mathematical Journal 59.1 (2009): 173-182. <http://eudml.org/doc/37915>.

@article{Hu2009,
abstract = {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.},
author = {Hu, Lili, Lai, Chunhui, Wang, Ping},
journal = {Czechoslovak Mathematical Journal},
keywords = {graph; degree sequence; potentially $K_5-H$-graphic sequence; graph; degree sequence; potentially -graphic sequence},
language = {eng},
number = {1},
pages = {173-182},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {On potentially $K_5-H$-graphic sequences},
url = {http://eudml.org/doc/37915},
volume = {59},
year = {2009},
}

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
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 59
IS - 1
SP - 173
EP - 182
AB - 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.
LA - eng
KW - graph; degree sequence; potentially $K_5-H$-graphic sequence; graph; degree sequence; potentially -graphic sequence
UR - http://eudml.org/doc/37915
ER -

References

top
  1. Bondy, J. A., Murty, U. S. R., Graph Theory with Applications, Macmillan Press (1976). (1976) MR0411988
  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. (1991) MR1170797
  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. (1999) MR1985076
  4. Gupta, G., Joshi, P., Tripathi, A., 10.1007/s10587-007-0042-z, Czech. Math. J. 57 (2007), 49-52. (2007) Zbl1174.05023MR2309947DOI10.1007/s10587-007-0042-z
  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., 10.1016/0012-365X(73)90037-X, Discrete Math. 6 (1973), 79-88. (1973) MR0327559DOI10.1016/0012-365X(73)90037-X
  10. Lai, Chunhui, A note on potentially K 4 - e graphical sequences, Australas J. Comb. 24 (2001), 123-127. (2001) Zbl0983.05025MR1852813
  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. (2007) Zbl1139.05016MR2322201
  13. Lai, Chunhui, An extremal problem on potentially K p , 1 , 1 -graphic sequences, Discret. Math. Theor. Comput. Sci. 7 (2005), 75-80. (2005) Zbl1153.05021MR2164060
  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. (1996) 
  17. Li, Jiong-Sheng, 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) Zbl0919.05058MR1644418DOI10.1002/(SICI)1097-0118(199810)29:2<63::AID-JGT2>3.0.CO;2-A
  18. Li, Jiong-sheng, Song, Zi-Xia, Luo, Rong, 10.1007/BF02879940, Sci. China (Ser. A) 41 (1998), 510-520. (1998) MR1663175DOI10.1007/BF02879940
  19. Li, Jiong-sheng, Yin, Jianhua, 10.1007/s100120100006, Southeast Asian Bull. Math. 25 (2001), 427-434. (2001) MR1933948DOI10.1007/s100120100006
  20. Luo, R., On potentially C k -graphic sequences, Ars Comb. 64 (2002), 301-318. (2002) MR1914218
  21. Luo, R., Warner, M., On potentially K k -graphic sequences, Ars Combin. 75 (2005), 233-239. (2005) Zbl1075.05021MR2133225
  22. Eschen, E. M., Niu, J., On potentially K 4 - e -graphic sequences, Australas J. Comb. 29 (2004), 59-65. (2004) Zbl1049.05027MR2037333
  23. Yin, J.-H., Li, J. S., 10.1016/j.disc.2005.03.028, Discrete Math. 301 (2005), 218-227. (2005) Zbl1119.05025MR2171314DOI10.1016/j.disc.2005.03.028
  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. (2005) MR2118998
  25. Yin, J.-H., Chen, G., On potentially K r 1 , r 2 , ⋯ , r m -graphic sequences, Util. Math. 72 (2007), 149-161. (2007) MR2306237
  26. Yin, M., 10.1007/s10255-006-0321-8, Acta Math. Appl. Sin., Engl. Ser. 22 (2006), 451-456. (2006) Zbl1106.05031MR2229587DOI10.1007/s10255-006-0321-8

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.