檢值圖論與度序列.pdf

1、中國(guó)科學(xué)技術(shù)大學(xué)博士學(xué)位論文檢值圖論與度序列姓名：尹建華申請(qǐng)學(xué)位級(jí)別：博士專業(yè)：應(yīng)用數(shù)學(xué)指導(dǎo)教師：李炯生2001.5.1AbstractExtremalgraphtheoryisanimportantresearchfieldingraphtheoryThisthesismainlyconsiderthevariationsofsomeclassicalTurantyperesultsandErd6s—S6sconjectureonco

2、ntainingtreeinextremalgraphtheory，andthecriterionsonpotentiallypropertyPorsubgraphHgraphicsequencesindegreesequencesThefollowingresultsareobtainedinthisthesis：1Erd6s，JacobsonandLehelconsideredavariationofclassicalTurjmth

3、eo—reinasfollows：Determinethesmallesteveninteger口(女，n)suchthateveryposi—rivegraphicn—termsequence7rwithtermsum盯(7r)≥盯(島，n)ispotentiallyKkl—graphicTheyconjecturedthat口(％，n)=(k一1)(2n—k)2forsumcientlylargenRecently，Li，Songa

4、ndLuoprovedthattheCOnjectureistruefork≥5andn≥(：)3，andraisedtheproblem：DeterminethesmallestpositiveintegerN(k)suchthattheconjectureholdsfork≥2andn≥Ⅳ(％)Theyalsopointedoutthat『盟尹1≤N(k)s(：)3Inthisthesis，wedeterminethevalueso

5、f∥(女，n)fork≥6andn≥2k3Theproblemfordeterminingthevaluesof口(南，n)iscompletelysolvedInaddition，weproveasacorollarythatN(k)=f學(xué)]fork262WefurtherconsiderthefollowingvariationofclassicalWoodalltheorem：Determinethesmallestevenint

6、eger口(3Cl，n)suchthateachgraphicn—termsequence7rwith盯(7r)≥盯(3cf，n)ispotentially3a—graphic，ie，7rhasarealizationcontainingcyclesCa，G，，qInthisthesis，thevaluesof口(3a，n)aredeterminedforl=2m一1，n≥3m一4andforl=2m，n≥5m一73Wealsocons

7、ideravariationoftheTurjnnumberez(Kr，，n)asfollows：Determinethesmallesteveninteger口(Kr，’n)suchthateverygraphicn—termSequence7廣with盯(7r)≥盯(Kr，，，n)ispotentially坼，一graphicInthisthesis，thevaluesof口(坼㈠n)aredeterminedforevenr，n≥

8、4r2一r一6andforoddr，n≥4r23r一84In1963Erd6sandSdsconjecturedthatifGisagraphofordernandsizee(a)withe(a)；n(女一1)，thenGcontainseverytreeToforderkIasitssubgraphInthisthesis，weprovetheCOnjectureinthiscasewherethecomplementofGdoesn

9、otcontainthecyclea5ThecriteriononthepotentiallyCrsgraphicsequencesisgivenandsomesufficientconditionsonthepotentiallyKrSgraphicsequencesarederivedInaddi—tion，wealsopresentthecriterionsonthepotentiallynearly2strongbipartit