Research On Factorable Bigraphic Pairs And Turán Number Of Star Forests

Let S=(a1,...,am;b1,...,bn),where a1,...,am and b1,...,bn are two sequences of non-negative integers.We say that S is a bigraphic pair if there exists a simple bipartite graph G with partite sets {x1,...,xm} and {y1,...,yn} such that dc(xi)=ai for 1?i?m and dc(yj)=bj for 1?j?n.In this case,we say that G is a realization of S.Analogous to Kundu's k-factor theorem,we show that if(a1,...,am;b1,...,bn)and(a1-e1,...,am-em;b1-f1,...,bn-fn)are two bigraphic pairs satisfying k?fi?k+1,1?i?n(or k?ei?k+1,1?i?m),for some 0?k?m-1(or 0?k?n-1),then(a1,...,am;b1,...,bn)has a realization containing an(e1,...,em;f1,...,fn)-factor.For m=n,we also give a necessary and sufficient condition for an(kn;kn)-factorable bigraphic pair to be connected(kn;kn)-factorable when k>2.This implies a characterization of bigraphic pairs with a realization containing a hamiltonian cycle.The Turán number of a graph H,denoted by ex(n,H),is the maximum number of edges of an n-vertex simple graph having no H as a subgraph.Let Sl denote the star on l+1 vertices,and let k·Sl denote k disjoint copies of Sl.Erdos and Gallai determined the value ex(n,k·S1)for all positive integers k and n.Yuan and Zhang determined the value ex(n,k·S2)and characterized all extremal graphs for all positive integers k and n.Lan et al.determined the value ex(n,2·S3)for all positive integers n.In this paper,we determine ex(n,2·Sl)for all positive integers l and n?3l+2 and ex(n,3·Sl)for all positive integers l and n?4l+3.Recently,we further determine ex(n,k·Sl)for all positive integers k,l and n,improving the result of Lidicky et al.