7293

6799

كارشناسي ارشد

رياضي كاربردي

اصفهان: دانشگاه صنعتي اصفهان، دانشكده علوم رياضي

1391

هشت، 55ص.: مصور، جدول، نمودار

ص.ع. به فارسي و انگليسي

1396/09/21

كتابنامه

علوم رياضي

رياضي

ID6799

به فارسي و انگليسي: قابل رويت در نسخه ديجيتالي

The Erdos Sos Conjecture on Some Families of Graphs Bentolhoda Majdi b majdibafruee@math iut ac ir August 25 2012 Department of Mathematical Sciences Isfahan University of Technology Isfahan 84156 83111 Iran Supervisor Dr Gholam Reza Omidi romidi@cc iut ac ir Advisor Dr Behnaz Omoomi bomoomi@cc iut ac ir 2010 MSC 05D10 Keywords Erd s S s conjecture Inclusion Tree Graph Abstract We investigate a problem in extremal graph theory known as the Erd s S s conjecture In 1959 n k 1 Erd s and Gallai proved every graph G of order n with e G contains a path with k edges 2Motivated by the result Erd s and S s made the following conjecture in 1963 n k 1 Erd s S s Conjecture ESC If G is a graph of order n with e G then G contains every 2tree T with k edges as a subgraph n k 1 n n k Note that e G if and only if e G Thus the Erd s S s conjecture can be 2 2restated as follows n n k Suppose that G is a graph of order n and T is any tree of size k If e G then G contains 2T as a subgraph However approximate versions of the conjecture were proved by Ajtai koml s and Szemer di usingthe Regularity Lemma They showed that for su ciently large k and su ciently large n ESC is truefor all graphs of order n that satisfy the hypothesis This conjecture is still open There are some partial results mainly on two directions on thisconjecture One is to pose conditions on the graph G In 1996 Brandt and Dobson showed that ESCholds for graphs with girth at least 5 Sacl and Wo niak improved this result and showed that ESC

غلامرضا اميدي

بهناز عمومي

سعيد اكبري، ابراهيم قرباني