Previous |  Up |  Next

Article

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
.

Files

Files Size Format View
CzechMathJ_72-2022-2_12.pdf 248.9Kb application/pdf View/Open
Back to standard record
Partner of
EuDML logo