| Title:
|
On potentially $K_5-H$-graphic sequences (English) |
| Author:
|
Hu, Lili |
| Author:
|
Lai, Chunhui |
| Author:
|
Wang, Ping |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
59 |
| Issue:
|
1 |
| Year:
|
2009 |
| Pages:
|
173-182 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
graph |
| Keyword:
|
degree sequence |
| Keyword:
|
potentially $K_5-H$-graphic sequence |
| MSC:
|
05C07 |
| MSC:
|
05C35 |
| idZBL:
|
Zbl 1224.05104 |
| idMR:
|
MR2486623 |
| . |
| Date available:
|
2010-07-20T14:59:15Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/140471 |
| . |
| Reference:
|
[1] Bondy, J. A., Murty, U. S. R.: Graph Theory with Applications.Macmillan Press (1976). MR 0411988 |
| Reference:
|
[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 |
| Reference:
|
[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 |
| Reference:
|
[4] Gupta, G., Joshi, P., Tripathi, A.: Graphic sequences of trees and a problem of Frobenius.Czech. Math. J. 57 (2007), 49-52. Zbl 1174.05023, MR 2309947, 10.1007/s10587-007-0042-z |
| Reference:
|
[5] Ferrara, M., Schmitt, R. Gould,J.: Potentially $K_s^t$-graphic degree sequences.Submitted. |
| Reference:
|
[6] Ferrara, M., Gould, R., Schmitt, J.: Graphic sequences with a realization containing a friendship graph.Ars Comb Accepted. |
| Reference:
|
[7] Hu, Lili, Lai, Chunhui: On potentially $K_5-C_4$-graphic sequences.Ars Comb Accepted. |
| Reference:
|
[8] Hu, Lili, Lai, Chunhui: On potentially $K_5-Z_4$-graphic sequences.Submitted. |
| Reference:
|
[9] Kleitman, D. J., Wang, D. L.: Algorithm for constructing graphs and digraphs with given valences and factors.Discrete Math. 6 (1973), 79-88. MR 0327559, 10.1016/0012-365X(73)90037-X |
| Reference:
|
[10] Lai, Chunhui: A note on potentially $K_4-e$ graphical sequences.Australas J. Comb. 24 (2001), 123-127. Zbl 0983.05025, MR 1852813 |
| Reference:
|
[11] Lai, Chunhui: An extremal problem on potentially $K_m-P_k$-graphic sequences.Int. J. Pure Appl. Math Accepted. |
| Reference:
|
[12] Lai, Chunhui: An extremal problem on potentially $K_m-C_4$-graphic sequences.J. Comb. Math. Comb. Comput. 61 (2007), 59-63. Zbl 1139.05016, MR 2322201 |
| Reference:
|
[13] Lai, Chunhui: An extremal problem on potentially $K_{p,1,1}$-graphic sequences.Discret. Math. Theor. Comput. Sci. 7 (2005), 75-80. Zbl 1153.05021, MR 2164060 |
| Reference:
|
[14] Lai, Chunhui, Hu, Lili: An extremal problem on potentially $K_{r+1}-H$-graphic sequences.Ars Comb Accepted. |
| Reference:
|
[15] Lai, Chunhui: The smallest degree sum that yields potentially $K_{r+1}-Z$-graphical sequences.Ars Comb Accepted. |
| Reference:
|
[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. |
| Reference:
|
[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. Zbl 0919.05058, MR 1644418, 10.1002/(SICI)1097-0118(199810)29:2<63::AID-JGT2>3.0.CO;2-A |
| Reference:
|
[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. MR 1663175, 10.1007/BF02879940 |
| Reference:
|
[19] Li, Jiong-sheng, Yin, Jianhua: A variation of an extremal theorem due to Woodall.Southeast Asian Bull. Math. 25 (2001), 427-434. MR 1933948, 10.1007/s100120100006 |
| Reference:
|
[20] Luo, R.: On potentially $C_k$-graphic sequences.Ars Comb. 64 (2002), 301-318. MR 1914218 |
| Reference:
|
[21] Luo, R., Warner, M.: On potentially $K_k$-graphic sequences.Ars Combin. 75 (2005), 233-239. Zbl 1075.05021, MR 2133225 |
| Reference:
|
[22] Eschen, E. M., Niu, J.: On potentially $K_4-e$-graphic sequences.Australas J. Comb. 29 (2004), 59-65. Zbl 1049.05027, MR 2037333 |
| Reference:
|
[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. Zbl 1119.05025, MR 2171314, 10.1016/j.disc.2005.03.028 |
| Reference:
|
[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 |
| Reference:
|
[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 |
| Reference:
|
[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. Zbl 1106.05031, MR 2229587, 10.1007/s10255-006-0321-8 |
| . |
