The potential-Ramsey numbers rpot (Cn, Kt-k) and rpot (Pn, Kt-k)

A nonincreasing sequence rho = (rho(1) , . . . , rho(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 rho. Given two graphs G(1) and G(2) , Busch et al. introduced the potential-Ramsey number of G(1) and G(2), denoted r(pot) (G(1), G(2)) , is the smallest nonnegative integer m such that for every m-term graphic sequence rho, there is a realization G of rho with G(1) subset of G or with G(2) subset of (G) over bar, where (G) over bar is the complement of G. For t >= 2 and 0 <= k <= (sic)t/2(sic), let K-t(-k) be the graph obtained from K-t by deleting k independent edges. Busch et al. determined r(pot) (C-n, K-t(-k)) and r(pot) (P-n, K-t(-k)) for k = 0. Du and Yin determined r(pot) (C-n, K-t(-k)) and r(pot)(P-n, K-t(-k)) for k = 1. In this paper, we further determine r(pot) (C-n, K-t(-k)) and r(pot) (P-n, K-t(-k)) for 2 <= k <= (sic)t/2(sic). (c) 2023 Elsevier Inc. All rights reserved.

Automated summary

The paper introduces the definition of the potential-Ramsey number r(pot)(G(1), G(2)) for two graphs G(1) and G(2), and determines its values for specific cases.