The Smallest Degree Sum That Yields Potentially Kr＋1 - K3-Graphic Sequences

Let a（Kr,＋1 - K3,n） be the smallest even integer such that each n-term graphic sequence п= （d1,d2,…dn） with term sum σ（п） = d1 ＋ d2 ＋…＋ dn 〉 σ（Kr＋1 -K3,n） has a realization containing Kr＋1 - K3 as a subgraph, where Kr＋1 -K3 is a graph obtained from a complete graph Kr＋1 by deleting three edges which form a triangle. In this paper, we determine the value σ（Kr＋1 - K3,n） for r ≥ 3 and n ≥ 3r＋ 5.

A Characterization for a Sequence to be Potentially K_(r+1) — e-graphic

Let n 〉 r, let lr --- （dl,d2,-,dn） be a non-increasing sequence of nonnegative integers and let Kr＋l - e be the graph obtained from Kr＋l by deleting one edge. If zr has a realization G containing Kr＋l - e as a subgraph, then r is said to be potentially Kr＋l - e-graphic. In this paper, we give a characterization for a sequence π to be potentially Kr＋l - e-graphic.

蕴含K_(r+1)-K_(1,t)可图序列的极值问题(英文)

序列S称为蕴含K_m-H可图序列如果S有一个实现包含K_m-H作为子图,本文给出了序列π∈GS_n是蕴含 K_(r+1)- K_(1,t)可图序列的充分条件.

Graphic Sequences and Split Graphs

The split graph Kr∨Ks on r＋s vertices is denoted by Sr,s A graphic sequence π = （d1, d2, …, dn） is said to be potentially Sr,s-graphic if there is a realization of π containing Sr,s as a subgraph. In this paper, a simple sufficient condition for π to be potentially Sr,s-graphic is obtained, which extends an analogous condition for π to be potentially Kr＋1-graphic due to Yin and Li （Discrete Math. 301 （2005） 218-227）. As an application of this condition, we further determine the values of δ（Sr,s, n） for n _≥3＋ 3s - 1.

A Rao-type Characterization for a Sequence to Have a Realization Containing an Arbitrary Subgraph H

Let G be an arbitrary spanning subgraph of the complete graph Kr＋1 on r＋1 vertices and Kr＋1-E（G） be the graph obtained from Kr＋1 by deleting all edges of G.A non-increasing sequence π=（d1,d2,...,dn） of nonnegative integers is said to be potentially Kr＋1-E（G）-graphic if there is a graph on n vertices that has π as its degree sequence and contains Kr＋1-E（G） as a subgraph.In this paper,a characterization of π that is potentially Kr＋1-E（G）-graphic is given,which is analogous to the Erdo s–Gallai characterization of graphic sequences using a system of inequalities.This is a solution to an open problem due to Lai and Hu.As a corollary,a characterization of π that is potentially Ks,tgraphic can also be obtained,where Ks,t is the complete bipartite graph with partite sets of size s and t.This is a solution to an open problem due to Li and Yin.

The Threshold for the Erdos,Jacobson and Lehel Conjecture to Be True

Let σ（k, n） be the smallest even integer such that each n-term positive graphic sequence with term sum at least σ（k, n） can be realized by a graph containing a clique of k ＋ 1 vertices. Erdos et al. （Graph Theory, 1991, 439-449） conjectured that σ（k, n） = （k - 1）（2n- k） ＋ 2. Li et al. （Science in China, 1998, 510-520） proved that the conjecture is true for k 〉 5 and n ≥ （k2） ＋ 3, and raised the problem of determining the smallest integer N（k） such that the conjecture holds for n ≥ N（k）. They also determined the values of N（k） for 2 ≤ k ≤ 7, and proved that [5k-1/2] ≤ N（k） ≤ （k2） ＋ 3 for k ≥ 8. In this paper, we determine the exact values of σ（k, n） for n ≥ 2k＋3 and k ≥ 6. Therefore, the problem of determining σ（k, n） is completely solved. In addition, we prove as a corollary that N（k） -= [5k-1/2] for k ≥6.