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...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.展开更多
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...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.展开更多
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 nonneg...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.展开更多
Gould R J等人考虑了下述经典Turan型极值问题的变形:对于给定的图H,确定最小的正偶数σ(H,n),使得对于每一个n项正可图序列π=(d1,d2,…,dn),当σ(π)=d1+d2+…+dn≥σ(H,n)时,π有一个实现G以H作为子图.本文完全确定了σ(K1,1,3,n)之...Gould R J等人考虑了下述经典Turan型极值问题的变形:对于给定的图H,确定最小的正偶数σ(H,n),使得对于每一个n项正可图序列π=(d1,d2,…,dn),当σ(π)=d1+d2+…+dn≥σ(H,n)时,π有一个实现G以H作为子图.本文完全确定了σ(K1,1,3,n)之值,其中Kr,s,t是r×s×t完全三部图.展开更多
基金Supported by the National Natural Science Foundation of China （No.10401010）.
文摘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.
基金Supported by the National Natural Science Foundation of China(No.11561017)Natural Science Foundation of Guangxi Province(No.2014GXNSFAA118361)Natural Science Foundation of Hainan Province(No.2016CXTD004)
文摘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.
基金Supported by National Natural Science Foundation of China(Grant No.11161016)
文摘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.
文摘Gould R J等人考虑了下述经典Turan型极值问题的变形:对于给定的图H,确定最小的正偶数σ(H,n),使得对于每一个n项正可图序列π=(d1,d2,…,dn),当σ(π)=d1+d2+…+dn≥σ(H,n)时,π有一个实现G以H作为子图.本文完全确定了σ(K1,1,3,n)之值,其中Kr,s,t是r×s×t完全三部图.
