| Title:
|
On potentially $H$-graphic sequences (English) |
| Author:
|
Yin, Meng-Xiao |
| Author:
|
Yin, Jian-Hua |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
57 |
| Issue:
|
2 |
| Year:
|
2007 |
| Pages:
|
705-724 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
graph |
| Keyword:
|
degree sequence |
| Keyword:
|
potentially $H$-graphic sequence |
| MSC:
|
05C07 |
| idZBL:
|
Zbl 1174.05024 |
| idMR:
|
MR2337625 |
| . |
| Date available:
|
2009-09-24T11:48:48Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/128200 |
| . |
| Reference:
|
[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 1170797 |
| Reference:
|
[2] Elaine Eschen and J. B. Niu: On potentially $K_4-e$-graphic.Australasian J. Combinatorics 29 (2004), 59–65. MR 2037333 |
| Reference:
|
[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 1985076 |
| Reference:
|
[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 1985084 |
| Reference:
|
[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. MR 0327559, 10.1016/0012-365X(73)90037-X |
| Reference:
|
[6] J. S. Li and Z. X. Song: An extremal problem on the potentially $P_k$-graphic sequences.Discrete Math. 212 (2000), 223–231. MR 1748652, 10.1016/S0012-365X(99)00289-7 |
| Reference:
|
[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. MR 1644418, 10.1002/(SICI)1097-0118(199810)29:2<63::AID-JGT2>3.0.CO;2-A |
| Reference:
|
[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. MR 1663175, 10.1007/BF02879940 |
| Reference:
|
[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. MR 1933948, 10.1007/s100120100006 |
| Reference:
|
[10] R. Luo: On potentially $C_k$-graphic sequences.Ars Combinatoria 64 (2002), 301–318. MR 1914218 |
| Reference:
|
[11] R. Luo and Morgan Warner: On potentially $K_k$-graphic sequences.Ars Combinatoria 75 (2005), 233–239. MR 2133225 |
| Reference:
|
[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. |
| Reference:
|
[13] A. R. Rao: An Erdős-Gallai type result on the clique number of a realization of a degree sequence, unpublished.. |
| Reference:
|
[14] J. H. Yin and J. S. Li: An extremal problem on potentially $K_{r,s}$-graphic sequences.Discrete Math. 260 (2003), 295–305. MR 1948398, 10.1016/S0012-365X(02)00765-3 |
| Reference:
|
[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. MR 2171314, 10.1016/j.disc.2005.03.028 |
| . |
