A further result on the potential-Ramsey number of G1 and G2


Jinzhi Du, Jianhua Yin




A non-increasing sequence pi = (d1, . . . , dn) 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 a graph H, a graphic sequence pi is 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 G1 and G2, the potential-Ramsey number rpot(G1,G2) is the smallest non-negative integer k such that for any k-term graphic sequence pi, either pi is potentially G1-graphic or the complementary sequence pi = (k − 1 − dk, . . . , k − 1 − d1) is potentially G2-graphic. They also gave a lower bound on rpot(G,Kr+1) for a number of choices of G and determined the exact values for rpot(Kn,Kr+1), rpot(Cn,Kr+1) and rpot(Pn,Kr+1). In this paper, we will extend the complete graph Kr+1 to the complete split graph Sr,s = Kr ∨ Ks. Clearly, Sr,1 = Kr+1. We first give a lower bound on rpot(G,Sr,s) for a number of choices of G, and then determine the exact values for rpot(Cn,Sr,s) and rpot(Pn,Sr,s)