On The Turán-type Problem Of Star Forests And Broom Graphs As Well As Related Issues

The Turan number of a graph G is ex(n,G)=max{e(H)|H is a G-free simple graph of order n}.Let the star of order l+1 be Sl,and the union of k disjoint star graphs be ∪i=1kSli.Lidick(?) et al.determined the value of ex(n,∪i=1kSli)when n is sufficiently large.This paper determines the value of ex(n,∪i=1kSli)when n≥Nk.Let eq(H)=∑i=1ndiq,here(d1,...,dn)is the degree sequence of graph H and q≥1 is an integer.A Turán-type problem of eq(H)is considered by Caro and Yuster:Given a graph Γ,let the function exq(n,Γ)=max{eq(H)|H/is a Γ-free graph of order n}Let l≥4,s≥0,Pl be a path of order l and Pl=v1v2…vl,Bl,s be Pl by adding s vertices u1,...,us which are adjacent to the vertex vl-1.The graph Bl,s is known as a Broom.This paper determines the value of ex(n,B8,s)when q≥2 and n is sufficiently large,which is the case of l=8 in a conjecture of the value of exq(n,Bl,s)proposed by Lan et al.Let π=(f1,...,fm;g1,...,gn),where f1,...fm and are two integer sequences with f1≥…≥fm≥0 and g1≥…≥ gn≥0.If there is a bipartite graph G=(X∪Y,E)such that f1,…,fm are the degrees of the vertices in X,gl,…,gn are the degrees of the vertices in Y,then the pair π=(f1,…,fm;g1,…,gn)is a bigraphic pair.Now,G is called a realization of π.If some realization of πcontains Ks,t,where s vertices in the part of size m and t vertices in the part of size n,then π is a potentially Ks,t-bigraphic pair.Ferrara et al.definedσ(Ks,t,m,n)to be the minimum integer k such that every bigraphic pairπ=(f1,…,fm;g1,…,gn)with σ(π)=f1+…+fm≥k is potentially Ks,t-bigraphic.They determined σ(Ks,t,m,n)for n≥m≥9s4t4.In this paper,we give two sufficient conditions to determine whether π is a potentially Ks,t-bigraphic pair and determine σ(Ks,t,m,n)when n≥m≥ s and n≥(s+1)t2-(2s-1)t+s-1,thus giving the solution of the problem proposed by Ferrara et al.