Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
graph; degree sequence; potentially $K_5-H$-graphic sequence
graph; degree sequence; potentially $K_5-H$-graphic sequence
Summary:
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.
References:
[1] Bondy, J. A., Murty, U. S. R.: Graph Theory with Applications. Macmillan Press (1976). MR 0411988
[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 1170797
[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 1985076
[4] Gupta, G., Joshi, P., Tripathi, A.: Graphic sequences of trees and a problem of Frobenius. Czech. Math. J. 57 (2007), 49-52. DOI 10.1007/s10587-007-0042-z | MR 2309947 | Zbl 1174.05023
[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 10.1016/0012-365X(73)90037-X | MR 0327559
[10] Lai, Chunhui: A note on potentially $K_4-e$ graphical sequences. Australas J. Comb. 24 (2001), 123-127. MR 1852813 | Zbl 0983.05025
[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 2322201 | Zbl 1139.05016
[13] Lai, Chunhui: An extremal problem on potentially $K_{p,1,1}$-graphic sequences. Discret. Math. Theor. Comput. Sci. 7 (2005), 75-80. MR 2164060 | Zbl 1153.05021
[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 10.1002/(SICI)1097-0118(199810)29:2<63::AID-JGT2>3.0.CO;2-A | MR 1644418 | Zbl 0919.05058
[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 10.1007/BF02879940 | MR 1663175
[19] Li, Jiong-sheng, Yin, Jianhua: A variation of an extremal theorem due to Woodall. Southeast Asian Bull. Math. 25 (2001), 427-434. DOI 10.1007/s100120100006 | MR 1933948
[20] Luo, R.: On potentially $C_k$-graphic sequences. Ars Comb. 64 (2002), 301-318. MR 1914218
[21] Luo, R., Warner, M.: On potentially $K_k$-graphic sequences. Ars Combin. 75 (2005), 233-239. MR 2133225 | Zbl 1075.05021
[22] Eschen, E. M., Niu, J.: On potentially $K_4-e$-graphic sequences. Australas J. Comb. 29 (2004), 59-65. MR 2037333 | Zbl 1049.05027
[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 10.1016/j.disc.2005.03.028 | MR 2171314 | Zbl 1119.05025
[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 2118998
[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 2306237
[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 10.1007/s10255-006-0321-8 | MR 2229587 | Zbl 1106.05031
Search
Partner of
