Open AccessA further result on the potential-Ramsey number of G1 and G2
Author(s) -
Jin-zhi Du,
Jianhua Yin
Publication year - 2019
Publication title -
filomat
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.449
H-Index - 34
eISSN - 2406-0933
pISSN - 0354-5180
DOI - 10.2298/fil1906605d
Subject(s) - combinatorics , ramsey's theorem , mathematics , graph , simple graph , sequence (biology) , discrete mathematics , upper and lower bounds , chemistry , mathematical analysis , biochemistry
A non-increasing sequence ? = (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 ?. Given a graph H, a graphic sequence ? is potentially H-graphic if ? 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 ?, either ? is potentially G1-graphic or the complementary sequence ? = (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).