A further result on the potential-Ramsey number of $G_1$ and $G_2$

Abstract

A non-increasing sequence
$\pi=(d_1,\ldots,d_n)$ of nonnegative integers is a {\it graphic
sequence} if it is realizable by a simple graph $G$ on $n$ vertices.
In this case, $G$ is referred to as a {\it realization} of $\pi$.
Given a graph $H$, a graphic sequence $\pi$ is {\it potentially
$H$-graphic} if $\pi$ has a realization containing $H$ as a
subgraph. Busch et al. (Graphs Combin., 30(2014)847--859) considered
a degree sequence analogue to classical graph Ramsey number as
follows: for graphs $G_1$ and $G_2$, the {\it potential-Ramsey
number} $r_{pot}(G_1,G_2)$ is the smallest non-negative integer $k$
such that for any $k$-term graphic sequence $\pi$, either $\pi$ is
potentially $G_1$-graphic or the complementary sequence
$\overline{\pi}=(k-1-d_k,\ldots,k-1-d_1)$ is potentially
$G_2$-graphic. They also gave a lower bound on $r_{pot}(G,K_{r+1})$
for a number of choices of $G$ and determined the exact values for
$r_{pot}(K_n,K_{r+1})$, $r_{pot}(C_n,K_{r+1})$ and
$r_{pot}(P_n,K_{r+1})$. In this paper, we will extend the complete
graph $K_{r+1}$ to the complete split graph
$S_{r,s}=K_r\vee\overline{K_s}$. Clearly, $S_{r,1}=K_{r+1}$. We
first give a lower bound on $r_{pot}(G,S_{r,s})$ for a number of
choices of $G$, and then determine the exact values for
$r_{pot}(C_n,S_{r,s})$ and $r_{pot}(P_n,S_{r,s})$.