Font Size: a A A

On The Tur(?)n Number Of Several Forests

Posted on:2018-09-03Degree:MasterType:Thesis
Country:ChinaCandidate:K ShiFull Text:PDF
GTID:2370330590477828Subject:Combinatorial mathematics
Abstract/Summary:PDF Full Text Request
Extremal graph theory is a main branch of graph theory.It studies ex-tremal graphs satisfying certain properties.The Turan number of a graph H ex(n,H)is the maximum number of edges in a graph G of order n which doesn't contain H as a subgraph.In 1941,Turan determined the value of ex(n,Kk)for k-complete graph.In 1959,Erdos and Gallai considered the Turan number for paths Pl and gave the upper bounds.In 2008,Balister proved the maximal number of edges for connected graphs not containing Pl.In 2013,Lidicky determined the Turan number of linear forests ?ik=1 Pli and star forests?ik=1 Sdi.At the end of the paper,Lidicky raised the problem on aPl ?Jt,but he didn't give the result and proof.This article considers the problem on ?ia-1 Pli ??i-1b Sdi and proves the Turan number and extremal graphs under certain conditions.Conclusion:Let F=(?)Pli?(?)Sdj,where a,b?1,l1?l2?…?la?4,d1?d2?…?db,(?)[li.2]>d1/2.Assume k=(?)[li/2]+b-1.For n sufficiently large,ex(n,F)=(2 k)+k(n-k)+cF CF=1 if all li are odd,otherwise 0.If one of li is even,the extremal graph is Kk+(?)n-k,otherwise Kk+(K2?(?)n-k-2).
Keywords/Search Tags:Tur(?)n number, extremal graph, path, star
PDF Full Text Request
Related items