A further result on the potential-Ramsey number of G1 and G2
Jin-zhi Du, Jianhua Yin
Abstract
Open-access reader
Jin-zhi Du, Jianhua Yin
Abstract
Open-access reader
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).
OpenAlex reports 2 citations for this work. Citation counts describe recorded attention and do not establish research quality.
A contribution statement is not available in the OpenAlex record.
Method details are not available in the OpenAlex metadata.
Findings are not separately available in the OpenAlex metadata.
Limitations are not available in the OpenAlex metadata.
Application details are not available in the OpenAlex metadata.
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).
Key concepts: Combinatorics, Ramsey's theorem, Mathematics, Graph, Simple graph, Sequence (biology), Discrete mathematics, Upper and lower bounds