A variation in the classical Turn extremal problem is studied. A simple graph G of order n is said to have property P k if it contains a clique of size k+1 as its subgraph. An n term nonincreasing nonnegative integer ...A variation in the classical Turn extremal problem is studied. A simple graph G of order n is said to have property P k if it contains a clique of size k+1 as its subgraph. An n term nonincreasing nonnegative integer sequence π=(d 1,d 2,...,d n) is said to be graphic if it is the degree sequence of a simple graph G of order n and such a graph G is referred to as a realization of π . A graphic sequence π is said to be potentially P k graphic if it has a realization G having property P k . The problem: determine the smallest positive even number σ(k,n) such that every n term graphic sequence π=(d 1,d 2,...,d n) without zero terms and with degree sum σ(π)=d 1+d 2+...+d n at least σ(k,n) is potentially P k graphic has been proved positive.展开更多
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完全三部图.展开更多
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.展开更多
A non-increasing sequenceπ=(d_1,d_2,···,d_n)of nonnegative integers is said to be potentially hamiltonian-graphic(resp.potentially pancyclic-graphic)if it is realizable by a simple graph on n vertices ...A non-increasing sequenceπ=(d_1,d_2,···,d_n)of nonnegative integers is said to be potentially hamiltonian-graphic(resp.potentially pancyclic-graphic)if it is realizable by a simple graph on n vertices containing a hamiltonian cycle(resp.containing cycles of every length from 3 to n).A.R.Rao and S.B.Rao(J.Combin.Theory Ser.B,13(1972),185–191)and Kundu(Discrete Math.,6(1973),367–376)presented a characterization ofπ=(d_1,d_2,···,d_n)that is potentially hamiltonian-graphic.S.B.Rao(Lecture Notes in Math.,No.855,Springer Verlag,1981,417–440,Unsolved Problem 2)further posed the following problem:present a characterization ofπ=(d_1,d_2,···,d_n)that is potentially pancyclic-graphic.In this paper,we first give solution to this problem for the case of 4≤n≤11.Moreover,we also show that a near regular graphic sequenceπ=(d_1,d_2,···,d_n)with dn≥3 is potentially pancyclic-graphic.展开更多
文摘A variation in the classical Turn extremal problem is studied. A simple graph G of order n is said to have property P k if it contains a clique of size k+1 as its subgraph. An n term nonincreasing nonnegative integer sequence π=(d 1,d 2,...,d n) is said to be graphic if it is the degree sequence of a simple graph G of order n and such a graph G is referred to as a realization of π . A graphic sequence π is said to be potentially P k graphic if it has a realization G having property P k . The problem: determine the smallest positive even number σ(k,n) such that every n term graphic sequence π=(d 1,d 2,...,d n) without zero terms and with degree sum σ(π)=d 1+d 2+...+d n at least σ(k,n) is potentially P k graphic has been proved positive.
文摘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.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.11561017)Natural Science Foundation of Hainan Province(Grant No.2016CXTD004)
文摘A non-increasing sequenceπ=(d_1,d_2,···,d_n)of nonnegative integers is said to be potentially hamiltonian-graphic(resp.potentially pancyclic-graphic)if it is realizable by a simple graph on n vertices containing a hamiltonian cycle(resp.containing cycles of every length from 3 to n).A.R.Rao and S.B.Rao(J.Combin.Theory Ser.B,13(1972),185–191)and Kundu(Discrete Math.,6(1973),367–376)presented a characterization ofπ=(d_1,d_2,···,d_n)that is potentially hamiltonian-graphic.S.B.Rao(Lecture Notes in Math.,No.855,Springer Verlag,1981,417–440,Unsolved Problem 2)further posed the following problem:present a characterization ofπ=(d_1,d_2,···,d_n)that is potentially pancyclic-graphic.In this paper,we first give solution to this problem for the case of 4≤n≤11.Moreover,we also show that a near regular graphic sequenceπ=(d_1,d_2,···,d_n)with dn≥3 is potentially pancyclic-graphic.
