| Title:
|
The potential-Ramsey number of $K_n$ and $K_t^{-k}$ (English) |
| Author:
|
Du, Jin-Zhi |
| Author:
|
Yin, Jian-Hua |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
72 |
| Issue:
|
2 |
| Year:
|
2022 |
| Pages:
|
513-522 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
A nonincreasing sequence $\pi =(d_1,\ldots ,d_n)$ of nonnegative integers is a graphic sequence if it is realizable by a simple graph $G$ on $n$ vertices. In this case, $G$ is referred to as a realization of $\pi $. Given two graphs $G_1$ and $G_2$, A. Busch et al. (2014) introduced the potential-Ramsey number of $G_1$ and $G_2$, denoted by $r_{\rm pot}(G_1,G_2)$, as the smallest nonnegative integer $m$ such that for every $m$-term graphic sequence $\pi $, there is a realization $G$ of $\pi $ with $G_1\subseteq G$ or with $G_2\subseteq \bar {G}$, where $\bar {G}$ is the complement of $G$. For $t\ge 2$ and $0\le k\le \lfloor \frac {t}{2}\rfloor $, let $K_t^{-k}$ be the graph obtained from $K_t$ by deleting $k$ independent edges. We determine $r_{\rm pot}(K_n,K_t^{-k})$ for $t\ge 3$, $1\le k\le \lfloor \frac {t}{2}\rfloor $ and $n\ge \lceil \sqrt {2k}\rceil +2$, which gives the complete solution to a result in J. Z. Du, J. H. Yin (2021). (English) |
| Keyword:
|
graphic sequence |
| Keyword:
|
potentially $H$-graphic sequence |
| Keyword:
|
potential-Ramsey number |
| MSC:
|
05C07 |
| MSC:
|
05C35 |
| idZBL:
|
Zbl 07547217 |
| idMR:
|
MR4412772 |
| DOI:
|
10.21136/CMJ.2022.0017-21 |
| . |
| Date available:
|
2022-04-21T19:03:56Z |
| Last updated:
|
2024-07-01 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/150414 |
| . |
| Reference:
|
[1] Bondy, J. A., Murty, U. S. R.: Graph Theory with Applications.American Elsevier, New York (1976). Zbl 1226.05083, MR 0411988 |
| Reference:
|
[2] Busch, A., Ferrara, M. J., Hartke, S. G., Jacobson, M. S.: A degree sequence variant of graph Ramsey numbers.Graphs Comb. 30 (2014), 847-859. Zbl 1298.05078, MR 3223948, 10.1007/s00373-013-1307-y |
| Reference:
|
[3] Busch, A., Ferrara, M. J., Hartke, S. G., Jacobson, M. S., Kaul, H., West, D. B.: Packing of graphic $n$-tuples.J. Graph Theory 70 (2012), 29-39. Zbl 1243.05191, MR 2916065, 10.1002/jgt.20598 |
| Reference:
|
[4] Du, J., Yin, J.: A further result on the potential-Ramsey number of $G_1$ and $G_2$.Filomat 36 (2019), 1605-1617. MR 4034026, 10.2298/FIL1906605D |
| Reference:
|
[5] Du, J.-Z., Yin, J.-H.: A new lower bound on the potential-Ramsey number of two graphs.Acta Math. Appl. Sin., Engl. Ser. 37 (2021), 176-182. Zbl 1464.05043, MR 4196622, 10.1007/s10255-021-0999-7 |
| Reference:
|
[6] Dvořák, Z., Mohar, B.: Chromatic number and complete graph substructures for degree sequences.Combinatorica 33 (2013), 513-529. Zbl 1313.05117, MR 3132924, 10.1007/s00493-013-2649-z |
| Reference:
|
[7] Erdős, P., Gallai, T.: Graphs with prescribed degrees of vertices.Mat. Lapok 11 (1960), 264-274 Hungarian. Zbl 0103.39701, MR 1964326 |
| Reference:
|
[8] Erdős, P., Jacobson, M. S., Lehel, J.: Graphs realizing the same degree sequences and their respective clique numbers.Graph Theory, Combinatorics and Applications. Vol. 1 John Wiley & Sons, New York (1991), 439-449. Zbl 0840.05093, MR 1170797 |
| Reference:
|
[9] Ferrara, M. J., Lesaulnier, T. D., Moffatt, C. K., Wenger, P. S.: On the sum necessary to ensure a degree sequence is potentially $H$-graphic.Combinatorica 36 (2016), 687-702. Zbl 1399.05038, MR 3597587, 10.1007/s00493-015-2986-1 |
| Reference:
|
[10] Ferrara, M. J., Schmitt, J.: A general lower bound for potentially $H$-graphic sequences.SIAM J. Discrete Math. 23 (2009), 517-526. Zbl 1215.05036, MR 2476846, 10.1137/080715275 |
| Reference:
|
[11] Gould, R. J., Jacobson, M. S., Lehel, J.: Potentially $G$-graphical degree sequences.Combinatorics, Graph Theory and Algorithms. Vol. I New Issues Press, Kalamazoo (1999), 451-460. MR 1985076 |
| Reference:
|
[12] Hakimi, S. L.: On realizability of a set of integers as degrees of vertices of a linear graph. I.J. Soc. Ind. Appl. Math. 10 (1962), 496-506. Zbl 0109.16501, MR 0148049, 10.1137/0110037 |
| Reference:
|
[13] Havel, V.: A remark on the existence of finite graphs.Čas. Pěstován{'ı Mat. 80 (1955), 477-480 Czech. Zbl 0068.37202, MR 0089165, 10.21136/CPM.1955.108220 |
| Reference:
|
[14] Rao, A. R.: The clique number of a graph with a given degree sequence.Proceedings of the Symposium on Graph Theory ISI Lecture Notes 4. Macmillan, New Delhi (1979), 251-267. Zbl 0483.05038, MR 0553948 |
| Reference:
|
[15] Robertson, N., Song, Z.-X.: Hadwiger number and chromatic number for near regular degree sequences.J. Graph Theory 64 (2010), 175-183. Zbl 1209.05098, MR 2674490, 10.1002/jgt.20447 |
| Reference:
|
[16] Yin, J., Li, J.: A variation of a conjecture due to Erdős and Sós.Acta Math. Sin., Engl. Ser. 25 (2009), 795-802. Zbl 1229.05161, MR 2505310, 10.1007/s10114-009-7260-2 |
| Reference:
|
[17] 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:
|
[18] Yin, J.-H., Meng, L., Yin, M.-X.: Graphic sequences and split graphs.Acta Math. Appl. Sin., Engl. Ser. 32 (2016), 1005-1014. Zbl 1410.05027, MR 3552867, 10.1007/s10255-016-0622-5 |
| . |
