Citation
New results on cycle structures in graphs

Material Information

Title:
New results on cycle structures in graphs
Place of Publication:
Denver, CO
Publisher:
University of Colorado Denver
Publication Date:
Physical Description:
electronic file (90 pages). : ;

Subjects

Subjects / Keywords:
Hamiltonian graph theory ( lcsh )

Notes

Review:
Determining if a graph has a hamiltonian cycle, a cycle using every vertex, is a classic NP-complete problem that has received a great deal of study. Here we look at two related cycle structural properties of graphs. Since a hamiltonian cycle is the longest possible cycle, one natural extension is to consider the question of whether a graph G on n vertices has a cycle of length i for each 3 ? i ? n. If a graph G does contain each of these possible cycle lengths, we say that G is pancyclic. A hamiltonian cycle can also be viewed as a single cycle that uses each vertex of G. Thus, a second way to extend the concept of hamiltonicity is to consider the question does a graph G contain k disjoint cycles that together use each vertex of G. Such a graph is said to contain a 2-factor with k cycles. Many sufficient conditions to guarantee a graph is hamiltonian have been found including conditions involving, among others, the minimum degree of a graph, connectivity of a graph, and forbidden subgraphs. Given a graph G and a family of graphs F, we say that G is F-free, or F is forbidden in G, if G contains no copy of any graph in F as an induced subgraph. Matthews and Sumner conjectured that every 4-connected, {K1,3}-free graph is hamiltonian. We characterize all graphs H such that every 4-connected, {K1,3, H}-free graph is also pancyclic.
Thesis:
Thesis (Ph.D.)--University of Colorado Denver. Applied mathematics
Bibliography:
Includes bibliographic references.
System Details:
System requirements: Adobe Reader.
General Note:
Department of Mathematical and Statistical Sciences

Record Information

Source Institution:
University of Colorado Denver
Holding Location:
|Auraria Library
Rights Management:
All applicable rights reserved by the source institution and holding location.
Resource Identifier:
898492295 ( OCLC )
ocn898492295

Downloads

This item is only available as the following downloads:


Full Text

PAGE 1

NEWRESULTSONCYCLESTRUCTURESINGRAPHS by TIMOTHYR.MORRIS M.S.,Mathematics,IllinoisStateUniversity,2008 B.S.,Physics,IllinoisStateUniversity,2002 Athesissubmittedtothe FacultyoftheGraduateSchoolofthe UniversityofColoradoinpartialfulllment oftherequirementsforthedegreeof DoctorofPhilosophy AppliedMathematics 2014

PAGE 2

ThisthesisfortheDoctorofPhilosophydegreeby TimothyR.Morris hasbeenapprovedforthe DepartmentofMathematicalandStatisticalSciences by MichaelFerrara,AdvisorandChair MichaelJacobson EllenGethner RonGould PaulWenger April29,2014 ii

PAGE 3

Morris,TimothyR.Ph.D.,AppliedMathematics NewResultsonCycleStructuresinGraphs ThesisdirectedbyAssociateProfessorMichaelFerrara ABSTRACT Determiningifagraphhasa hamiltoniancycle ,acycleusingeveryvertex,isa classicNP-completeproblemthathasreceivedagreatdealofstudy.Herewelook attworelatedcyclestructuralpropertiesofgraphs.Sinceahamiltoniancycleisthe longestpossiblecycle,onenaturalextensionistoconsiderthequestionofwhethera graph G on n verticeshasacycleoflength i foreach3 i n .Ifagraph G does containeachofthesepossiblecyclelengths,wesaythat G ispancyclic.Ahamiltonian cyclecanalsobeviewedasasinglecyclethatuseseachvertexof G .Thus,asecond waytoextendtheconceptofhamiltonicityistoconsiderthequestiondoesagraph G contain k disjointcyclesthattogetheruseeachvertexof G .Suchagraphissaid tocontaina 2-factorwith k cycles Manysucientconditionstoguaranteeagraphishamiltonianhavebeenfound includingconditionsinvolving,amongothers,theminimumdegreeofagraph,connectivityofagraph,andforbiddensubgraphs.Givenagraph G andafamilyof graphs F ,wesaythat G is F -free,or F isforbiddenin G ,if G containsnocopy ofanygraphin F asaninducedsubgraph.MatthewsandSumnerconjecturedthat every4-connected, f K 1 ; 3 g -freegraphishamiltonian.Wecharacterizeallgraphs H suchthatevery4-connected f K 1 ; 3 ;H g -freegraphisalsopancyclic. Brandtetal.[Brandt,Chen,Faudree,Gould,Lesniak.DegreeConditionsfor 2-factors,J.GraphTheory,24:165{173,1997]showedthatagraph G on n 4 k verticeswithminimumdegreeatleast G n 2 containsa2-factorwith k cycles. Thisdegreeconditionisexactlythesameastheminimumdegreeconditionsucient iii

PAGE 4

toguaranteethat G containsahamiltoniancycle.Weshowthatif G isknownto behamiltonian,thisminimumdegreeconditioncanbeimprovedbyshowingthe following.For k 1and0 1 10 ,if G isahamiltoniangraphon n 3 k vertices withminimumdegree G )]TJ/F18 7.9701 Tf 6.675 -4.976 Td [(2 5 + n ,then G containsa2-factorwith k cycles. Theformandcontentofthisabstractareapproved.Irecommenditspublication. Approved:MichaelFerrara iv

PAGE 5

DEDICATION Tomyparents,whoalwaysencouragedmycuriosityandurgedmetothinkfor myself. v

PAGE 6

ACKNOWLEDGMENT Iwouldliketothankmyadvisor,MikeFerrara,foralwayspushingmetodomore, andalsoMikeJacobson,EllenGethner,RonGould,andPaulWengerforservingon mycommitteeandsupportingmyresearch. Researchisnotdoneinavacuum,andwhileIcannotthankeveryonewhohelped mealongtheway,Iwouldliketoacknowledgemyocematesandclassmates.Inparticular,IwouldliketoacknowledgeCathyErbes,HencBouwmeester,EricSullivan, BreeanneFlesch,JennyDiemunsch,BrentThomas,andAxelBrandt.Thesepeople showedmegreatunderstandingandgavemesupportwhileIexperiencedthefrustrationsnaturaltotheprocessofearningaPh.D.Theyalsogavememathematicaland technicalhelpateverystepoftheprocess.Finally,IwouldliketothankRochelle Hinmanforunderstandingmystressduringthenalyearandhelpingmetokeepmy prioritiesstraight. IwouldliketoacknowledgethefundingIreceivedthroughtheUCDGK12 TransformingExperiencesProject,NSFaward#0742434,NSFawardDMS08-38434 MSW-21-MCTP:ResearchExperienceforGraduateStudents",andsupportthrough theLynnBatemanMemorialFellowship. vi

PAGE 7

TABLEOFCONTENTS Figures.......................................ix Chapter 1.Introduction...................................1 2.CyclesinGraphs................................5 2.1Hamiltonicity..............................5 2.1.1NecessaryConditionsforHamiltonicity.............6 2.1.2SucientConditionsforHamiltonicity.............6 2.2Pancyclicity...............................11 2.32-Factors.................................13 2.42-Factorswith k components......................15 3.ForbiddenSubgraphsforPancyclicity.....................17 3.14-connectedGraphs...........................18 3.2ProofofTheorem3.4..........................19 4.Pancyclicityof f K 1 ; 3 ;P 10 g -freegraphs.....................25 4.1LongCycles...............................25 4.2ShortCycles...............................29 5.Pancyclicityof f K 1 ; 3 ;N ; 2 ; 2 g -freegraphs.................40 5.1ShortCycles...............................40 5.2TechnicalLemmas............................46 5.34-connected f K 1 ; 3 ;N ; 2 ; 2 g -freegraphsarepancyclic........60 6.2-factorsinHamiltonianGraphs........................65 6.1Introduction...............................65 6.2ProofofTheorem6.6..........................66 7.FutureWork...................................72 7.1DirectExtensions............................72 7.2LocalChvatal-Erd}os...........................73 vii

PAGE 8

7.3OtherDirections.............................75 References ......................................76 viii

PAGE 9

FIGURES Figure 1.1ExamplesofSmallGraphs..........................2 1.2Formingthelinegraphof G fromthegraph G ...............4 2.1TheIcosianboardwithahamiltoncycleshown...............5 2.2Adensenon-hamiltoniangraph.......................7 2.3Forbiddensubgraphsforhamiltonicityin2-connectedgraphs.......10 2.4Forbiddensubgraphsforpancyclicityin2-connectedgraphs........13 2.5Forbiddensubgraphsfor2-factorsin2-connectedgraphs..........14 3.1Forbiddensubgraphsforpancyclicityin3-connectedgraphs........18 3.2Some4-connectedgraphsthatarenotpancyclic..............20 3.3A4-connected,claw-freegraphwithno17-cycle..............23 4.1A t -cycleina4-connected f K 1 ; 3 ;P 10 g -freegraph..............27 4.2Thesets A B ,and D ina t -cycleina4-connected f K 1 ; 3 ;P 10 g -freegraph.28 4.3TwodrawingsofthelinegraphofthePetersengraph...........33 4.4Findinga5-cycle...............................34 4.5Necessarysubgraphsusedtoshowcyclesoflength6through8......36 4.6Structureusedtoshowagraphhascyclesoflength6through8.....37 5.1Deningthe notation...........................40 5.2 f K 1 ; 3 ;N ; 2 ; 2 g -freegraphshave4-and5-cycles.............44 5.3Thefan F whennoneof x 0 y 0 ,or z 0 ison C .................47 5.4Thefan F when z 0 ison C ,butneither x 0 nor y 0 ison C ..........47 5.5Thefan F whenboth y 0 and z 0 areon C ,but x 0 isnoton C ........48 5.6Formingan s +3-cycle...........................57 5.7Findinganinducedcopyof N ; 1 ; 1forLemma5.7............60 5.8AninducedFanoan s -cycle.........................61 6.1Partitioningtheedgesofaconvexgeometricgraph.............68 ix

PAGE 10

6.2Aconvexgeometricgraph..........................70 x

PAGE 11

1.Introduction A hypergraph G isapair G = V G ;E G whereeachedge,anelementof E G ,isassociatedwithanunorderedtupleofvertices.Theset V G iscalledthe vertexset of G while E G isthe edgeset .Ifeachedgeisassociatedwithapair ofvertices,wecall G a 2-uniformhypergraph andcallthepairofverticesassociated withanyedge e 2 E G the endpoints of e .Ifeachedgeofa2-uniformhypergraph isanorderedpairwesaythat G isa directedgraph ,ifeachedgeisunordered,then G isan undirectedgraph .Edgesofa2-uniformhypergraphthatareassociatedwith thesamepairofverticesarereferredtoas multipleedges .Finally,anyedgethat hasbothendpointsthesamevertexiscalleda loop .Werefertoanundirected2uniformhypergraphwithoutmultipleedgesorloopsasa simplegraph .Throughout theremainderofthisdocument,wewillprimarilyconsidersimplegraphsand,forthe sakeofsimplicity,anytimewesay graph wewillmeanasimplegraph. Thusagraphisanirreexive,anti-symmetric,binaryrelationwhosedomainand co-domainareequal.The order ofagraph G = V G ;E G is j V G j whilethe size of G is j E G j .Frequentlywerefertoagraphoforder n asagraphon n vertices. Anedge e issaidtobe incident toavertex v if v isanendpointof e .Twovertices u and v are adjacent ifthereisanedgeincidenttoboth u and v .Inthiscasewewrite that u v or uv 2 E G .Also,the neighborhood of u ,denoted N G u isthesetofall vertices v of G suchthat u v .The closedneighborhood of u is N G [ u ]= N G u [f u g The degree of u ,denotedby deg u isthenumberofedgesincidentto u Twographs G and H aresaidtobe isomorphic ,denoted G = H ,ifthereexistsa function : V G V H suchthatforanytwovertices u;v 2 V G wehavethat u v 2 E H ifandonlyif uv 2 E G .Whenwestudysomegraph G weare typicallyinterestedinallgraphsisomorphicto G .Forthisreasonwewillfrequently writethat G is H ,or G isacopyof H ,if G = H A subgraph H of G ,denoted H G ,isagraphsuchthat V H V G and 1

PAGE 12

E H E G wherebothendpointsofeveryedgein E H arein V H .If H G thenwesaythat G contains H asasubgraph or,forthesakeofbrevity,simply G contains H .For H G ,if V H = V G ,thenwesaythat H isa spanning subgraphof G ,orsimplythat H spans G .Ontheotherhand,ifeveryedgeof G with bothendpointsin V H isalsoanedgein E H ,thenwesaythat H isan induced subgraphof G .Notethatthismeansthataninducedsubgraph H of G canfully describedbyitsvertexset.Thus,givenaset S V G wewrite h S i G todenotethe inducedsubgraphof G withvertexset S ;inthiscasewesaythat S induces h S i G Forconvenience,wewilloftendenote h V G )]TJ/F20 11.9552 Tf 11.955 0 Td [(S i G simplyas G )]TJ/F20 11.9552 Tf 11.955 0 Td [(S Wecangaininsightintothestructureofagraph G byunderstandingthesubgraphsof G .Severalgraphsareofparticularinterestindescribingthestructure ofagraph.A pathon k vertices ,denoted P k ,isagraphwithvertexset V P k = f v 1 ;v 2 ;:::;v k g andedgeset E G = f e 1 ;e 2 ;:::;e k )]TJ/F18 7.9701 Tf 6.587 0 Td [(1 g suchthat e i = f v i ;v i +1 g for each1 i k )]TJ/F15 11.9552 Tf 12.238 0 Td [(1seeFigure1.1.Thevertices v 1 and v k aresaidtobethe endpoints ofthepath.The length ofapathisthenumberofedgesinthepath,so P k haslength k )]TJ/F15 11.9552 Tf 11.882 0 Td [(1.A cycleon k vertices ,ormoresimplya k -cycle,denoted C k ,isthe graphformedfrom P k byaddingtheedge v k v i seeFigure1.1.Anothersignicant graphisthe complete graphon n verticeswhichisdenoted K n .Thisgraphisdened sothat V K n = f v 1 ;v 2 ;:::;v n g andthereisanedge v i v j foreach i 6 = j .Theempty graphon n vertices,denoted K n ,isagraphwith n verticesandnoedges. P 4 C 5 K 5 K 5 Figure1.1:Apathon4vertices,a5-cycle,acompletegraphon5 vertices,andanemptygraphon5vertices. If u and v areverticesof G andthereisasubgraph P of G isomorphictoapath 2

PAGE 13

withendpoints u and v ,thenwesaythat P isa u;v -pathin G .Agraph G issaid tobe connected ifforeverypair u;v ofverticesin V G thereisa u;v -path.A component of G isamaximalconnectedsubgraphof G ,thusaconnectedgraphisa graphwithonlyonecomponent.A cut-set of G isaset S V G suchthat G )]TJ/F20 11.9552 Tf 12.077 0 Td [(S isnotconnected.Agraph G has connectivity k ,denoted G = k if G isconnected andaminimumordercut-setof G has k vertices.Agraph G issaidtobe k -connected if G k If T isaconnectedgraphthathasnosubgraphisomorphictoacycle,wesaythat T isa tree .Ifeverycomponentofagraph G isatree,thenwesaythat G isa forest The girth ofagraph G ,denoted g G ,isthelengthoftheshortestcycleof G ;if G isaforest,thenwesaythat g G = 1 .The circumference of G isthelengthofa longestcyclein G andisdenoted c G .If G hasnocycle,then c G =0. An independentset inagraph G isaset S V G suchthat h S i G isisomorphic to K j S j .The independencenumber ofagraph G ,denoted G ,isthesizeofthe largestindependantsetin G .Ifthereisaset S V G suchthat h S i G = K j S j ,then wesatthat S inducesa clique in G .The cliquenumber of G isthesizeofthelargest S V G suchthat S inducesaclique;thecliquenumberof G isdenoted G The density ofagraph G isgivenby j E G j n 2 .Wecanalsodiscussthedensityofa familyofgraphs.Let F beaninnitefamilyofgraphssuchthatforall n thereisa graph G n 2F suchthat j G n j n .Further,let n betheminimumdensityamong allgraphsin F withorderatleast n .Dene n analagouslyexceptforthemaximum density.Wesaythefamily F is dense iflim n !1 n =1while F is sparse iflim n !1 n =0. Informally,wewillwritethataspecicgraphisdenseifithasdensitycloseto1and callitsparseifithasdensitycloseto0. Givenagraph G ,the linegraphof G ,denoted L G ,istheincidencegraphofthe edgesof G .Thatis, L G isthegraphwithvertexset E G suchthattwovertices e 1 and e 2 in V L G = E G areadjacentin L G ifandonlyif e 1 sharesanendpoint 3

PAGE 14

with e 2 in G seeFigure1.2. G L G superimposedon G L G Figure1.2:Formingthelinegraphof G fromthegraph G Weconcludethissectionwithafamilyofgraphsthatareofparticularinterestfor theirubiquityinawide-varietyofgraphsettings.A bipartite graphisagraphwhose vertexsetcanbepartitionedintotwoindependantsetsreferredtoas partitesets Onesignicantcharacterizationofbipartitegraphsisthatagraph G isbipartiteif andonlyif G containsnocycleofoddlength.If G isabipartitegraphwithpartite sets A ofsize m and B ofsize n suchthatforevery a 2 A and b 2 B thereisanedge ab ,then G isa completebipartitegraph ;wedenotethecompletebipartitegraphas K m;n 4

PAGE 15

2.CyclesinGraphs 2.1Hamiltonicity In1857SirWilliamRowanHamiltoninventedtheIcosian"game,whichlaid outthedodecahedrononawoodenblockwithaholerepresentingeachvertex.see Figure2.1Gameplayconsistedofplacingapeginanyholeand,onsubsequent turns,placingapeginanunusedholeneighboringthemostrecentlyplacedpeg.The goalwastoplaceapegineveryholeandendinaholeneighboringyourstartinghole. Inotherwords,thegoalwastondaspanningcycle. Figure2.1:TheIcosianboardwithahamiltoncycleshown. Suchaspanningcycleiscalleda hamiltoncycle andagraph G issaidtobe hamiltonian ifitcontainsahamiltoncycle.Theproblemofdeterminingifagraphis hamiltonianisawell-studied,NP-complete 1 problem[32].Ifagraphhasmaximum degree2,thenitiseasytocheckifitishamiltonian.However,evenif G hasmaximum degree3,thedeterminationremainsverydicult[33]. Theorem2.1 Garey,Johnson,Stockmeyer,1976 If G isagraphwithmaximum degree3,thendeterminingif G ishamiltonianisNP-complete. 1 AbooleandecisionproblemissaidtobeNPif,givenasuitablesolutiontoken,asolutioncan beveriedinpolynomialtime.TheproblemissaidtobeNP-completeifitisintheclassNPanda polynomialtimealgorithmtodeterminethesolutioncanbemodiedtoapolynomialtimealgorithm todeterminethesolutionforeveryproblemintheclassNP. 5

PAGE 16

InlightofTheorem2.1,muchresearchhasgoneintondingbothnecessary conditionsforagraphtobehamiltonianandalsosucientconditionstoguarantee agraphishamiltonian.Webeginbylookingatsomenecessaryconditions. 2.1.1NecessaryConditionsforHamiltonicity Ifagraphishamiltonian,thenremovinganyvertexleavesapaththatpasses througheveryremainingvertex.Thuswegetthefollowingtwopropositionsdirectly. Proposition2.2. Everyhamiltoniangraphis2-connected. Proposition2.3. Everyhamiltoniangraph G hasminimumdegree G 2 Foranygraph G ,let k G denotethenumberofcomponents.Wesaythata graph G is t -tough if,foreach S V G ,wehavethat k G )]TJ/F20 11.9552 Tf 11.955 0 Td [(S j S j t Proposition2.4. Everyhamiltoniangraphis1-tough Proof: Suppose G isahamiltoniangraphwithhamiltoncycle v 1 v 2 :::v n v 1 and S V G .If S = V G ,thentheresultistrivial,sosuppose S G .Let k = j S j and assumethattheindicesonthehamiltoncyclewerechosensothat v n 2 S ,but v 1 = 2 S Let i 1
PAGE 17

K n )]TJ/F18 7.9701 Tf 6.587 0 Td [(3 k +2 v 1 v 2 v 3 v 2 k )]TJ/F18 7.9701 Tf 6.586 0 Td [(1 K k )]TJ/F18 7.9701 Tf 6.586 0 Td [(1 Figure2.2:Anycyclecontainsatmosttwoof f v 1 ;v 2 ;v 3 g Figure2.2whichhasdensityapproaching1as n approachesinnity.Thus,weneed toalsohaveaconditionthatensurestheedgesarenicely"distributed.Oneway todothisistoforceeveryvertextohavemanyneighbors.Perhapsthebestknown exampleofthistypeofconditionisthefollowing[16]. Theorem2.5 Dirac,1952 Foragraph G on n 3 vertices,if G n 2 ,then G ishamiltonian. Theorem2.5strengthensthenecessaryconditiongiveninProposition2.3toproduceasucientcondition.Shortlythereafter,Orewasabletoweakenthiscondition usingadegreesumcondition.Let 2 G =min f deg u + deg v j u 6 = v;u 6 v g .Ore showedthefollowing[55]. Theorem2.6 Ore,1960 Foragraph G on n vertices,if 2 G n ,then G is hamiltonian. Ore'sconditionallowsforasmallcliquecomposedofverticesoflowdegreeas longastheverticesintherestofthegraphallhavehighenoughdegree.Theideas usedinprovingthedegreeconditionsinTheorems2.5and2.6canalsobeusedto deneaclosureoperation. 7

PAGE 18

Denition2.7. Theclosureof G ,denoted cl B G ,isthegraphformedfrom G by iterativelyaddingedgesconnectingtwononadjacentverticeswhosedegreesumisat least j V G j untilnosuchpairofverticesremains. Theclosureisavaluabletoolforstudyinghamiltonicityduetothefollowing theoremofBondyandChvatal[5]. Theorem2.8. Agraph G ishamiltonianifandonlyif cl B G ishamiltonian. Eachoftheseconditionsisbasedoncontrollingthedegreesoftheverticesof agraphandthuscanbeseenasstrengtheningthenecessaryconditioninProposition2.3.Othernecessaryconditionscanalsobestrengthenedtoformsucient conditions. Suppose G isagraphand S V G .If k G )]TJ/F20 11.9552 Tf 12.874 0 Td [(S = k ,then G k ,as selectingonevertexfromeachcomponentof G )]TJ/F20 11.9552 Tf 12.209 0 Td [(S producesanindependentsetin G .Thus,thestatementthat G G isstrongerthanbeing1-tough.Chvatal andErd}os[15]usedthisstrengtheningofthenecessaryconditioninProposition2.4 byshowingthefollowing. Theorem2.9. If G isagraphon n 3 verticessuchthat G G ,then G is hamiltonian. WehaveseenthatthenecessaryconditionsinPropositions2.3and2.4maybe strengthenedtoprovideasucientconditiontoguaranteeagraphishamiltonian. Onemightexpectthatthesamecouldbedonewiththeconnectivityconditionin Proposition2.2,howeverthegraph K m;n with m
PAGE 19

graphs,agraph G issaidtobe F -free if G containsnomemberof F asaninduced subgraph.Sinceeach K s;r contains s inducedcopiesof K 1 ;r ,itmakessensetolook atgraphsthatare K 1 ;r -free.Anygraphonatleastthreeverticesthatis K 1 ; 2 -freeis completeandthusishamiltonian.Thus,welookat K 1 ;r -freegraphswith r 3.We referto K 1 ; 3 asthe claw ,if G is F -freeforsomefamily F and K 1 ; 3 2F ,then G is saidtobe claw-free Wealsofrequentlyforbidgraphsfromthefamilyof generalizednets denoted N i;j;k consistingofatrianglewhereeachvertexisidentiedwiththeendpointof a P i +1 P j +1 ,and P k +1 respectivelyseeFigure2.3forthreeexamples.Goodman andHedetniemi[35]showedthefollowing. Theorem2.10. Every2-connected f K 1 ; 3 ;N ; 0 ; 0 g -freegraphishamiltonian. Thistheorembeganstudyintopairsofforbiddensubgraphsthatwouldimplya2-connectedgraphishamiltonian.In1981,Duusetal.[18]showedthat f K 1 ; 3 ;N ; 1 ; 1 g -freesuced.Thefollowingyearssawaprogressionshowingthat f K 1 ; 3 ;N ; 0 ; 0 g -free[40], f K 1 ; 3 ;P 6 g -free[11],and f K 1 ; 3 ;N ; 1 ; 0 g -free[3]suced. Bedrossian[3]showedthattheseresultscharacterizedallpairsofforbiddensubgraphs thatimplya2-connectedgraphishamiltonian. Fouryearslater,Faudreeetal.[23]showedthatif G hasorder n 10,forbiddingthepair f K 1 ; 3 ;N ; 0 ; 0 g alsoimpliesthata2-connectedgraphishamiltonian. FaudreeandGould[24]thenextendedBedrossian'scharacterizationtocharacterize thepairsofforbiddensubgraphsthatimplya2-connectedgraphon n 10vertices ishamiltonian. Theorem2.11. Let X and Y beconnectedgraphssuchthat X;Y 6 = P 3 .Every2connected f X;Y g -freegraphoforder n 10 ishamiltonianifandonlyif X isthe clawand Y isaninducedsubgraphofoneof f N ; 1 ; 1 ;N ; 1 ; 0 ;N ; 0 ; 0 ;P 6 g see Figure2.3 9

PAGE 20

N ; 1 ; 1 N ; 1 ; 0 N ; 0 ; 0 P 6 Figure2.3:Anygraphthatis2-connected,claw-freeanddoesnot containanyofthesegraphsasaninducedsubgraphishamiltonian. Theorem2.11saysthatwemustforbidmorethanjusttheclawtoguaranteea 2-connectedgraphishamiltonian.Thisleavesopenthequestion,istherea k such thatevery k -connectedclaw-freegraphishamiltonian.MatthewsandSumner[52] conjecturedthefollowingwhichhasprovidedtheimpetusforagreatdealofresearch intothehamiltonicityofclaw-freegraphs. Conjecture2.12 TheMatthews-SumnerConjecture If G isa4-connectedclawfreegraph,then G ishamiltonian. In[59],Ryjacekdenedaclosureoperationforclaw-freegraphstodemonstrate thatthisisequivalenttoaconjectureofThomassen[66]thatevery4-connectedline graphishamiltonian.Let G beaclaw-freegraph.If v isavertexsuchthat N v is connected,butnotcomplete,wesaythat v is eligible .Dene cl R G tobethegraph formedbyiterativelyaddingallmissingedgestotheneigborhoodofeligiblevertices in G until G hasnoeligiblevertices.Ryjacek[59]showedthefollowing. Theorem2.13. Let G beaclaw-freegraph.Thefollowingarealltrue. 1. cl R G isuniquelydened. 2. cl R G isthelinegraphofatriangle-freegraph. 3.Thelongestcyclein cl R G hasthesamelengthasthelongestcyclein G 10

PAGE 21

Wesaythatagraphproperty P is stableunderRyjacek'sclosure ifaclaw-free graph G hasproperty P ifandonlyif cl R G hasproperty P .Thustheproperty ishamiltonian"isstableunderRyjacek'sclosure.Thestabilityofhamiltoniantype propertiesunderseveralclosureconceptshavebeenstudiedandmanyoftheseresults aresurveyedin[10]. In[59],Ryjacekusedthefactthathamiltonicityisstabletoextendaresult on7-connectedlinegraphs[44]toshowthatevery7-connected,claw-freegraphis hamiltonian.Sincethen,KaiserandVrana[45]haveshownthefollowingwhich representsthebestgeneralprogresstowardarmingConjecture2.12. Theorem2.14. Every5-connected,claw-freegraphwithminimumdegreeatleast6 ishamiltonian. Itisworthnotingthatthepropertyisclaw-free"isalocalpropertyinthesense thatitcanbecheckedbyexaminingeachvertexanditsneighborhoodindividually. Thusthepropertycanbecheckedinpolynomialtime.Similarlyforagraphon n vertices,thepropertyis k -connectedcanbecheckedin O n k +1 time.Thiscanbe seenbythefactthatthereare )]TJ/F21 7.9701 Tf 10.632 -4.379 Td [(n k )]TJ/F18 7.9701 Tf 6.587 0 Td [(1 = O n k )]TJ/F18 7.9701 Tf 6.586 0 Td [(1 subgraphsof G with k )]TJ/F15 11.9552 Tf 12.227 0 Td [(1vertices removedandyoucancheckifeachoftheseisconnectedin O n 2 timebyanalgorithm givenbyHopcroftandTarjan[43]thattheydescribeaswell-known".Thus,while theproblemofdeterminingifagraph G ishamiltonianisNP-complete,theforbidden subgraphconditionsthataresucienttoguarantee G ishamiltoniancanbechecked inpolynomialtime. Thehamiltonianproblemhasledtoanumberofextensionsandrelatedproblems. Manyoftheseproblemsandknownresultsonthemaresurveyedin[36,37,39].In Sections2.2,2.3,and2.4weintroducethreesuchextensions. 2.2Pancyclicity Agraph G on n verticesissaidtobe pancyclic if,foreach3 i n G containsacycleoflength i .Thuseverypancyclicgraphishamiltonian,butnot 11

PAGE 22

everyhamiltoniangraphispancycliceg. C k for k 4.Aswithdeterminingifa graphishamiltonian,determiningifagraphispancyclicisNP-complete[48].Since apancyclicgraphisnecessarilyhamiltonian,thenecessaryconditionsforagraphto behamiltoniangiveninPropositions2.2,2.3,and2.4arealsonecessaryconditions foragraphtobepancyclic.Further,anyconditionsucienttoguaranteeagraph G ispancyclicisalsosucienttoguaranteethat G ishamiltonian.Withthisin mind,itmakessensetoexaminehowmuchwemuststrengthentheconditionsgiven byTheorems2.5,2.9,and2.11togetconditionssucienttoguaranteeagraphis pancyclic. Surprisingly,wheninvestigatingDirac'sminimumdegreecondition,Bondy[4] showedthefollowing. Theorem2.15. If G isagraphoforder n 3 withminimumdegree n 2 ,then G iseitherpancyclicor G isisomorphicto K n 2 ; n 2 Thus,withthesingleexceptionofthecompletebalancedbipartitegraph,Dirac's sucientconditionforhamiltonicityisalsosucienttoguaranteeagraphispancyclic. Basedonthistheorem,Bondymadethefollowingmeta-conjecture. Conjecture2.16 Bondy'smeta-conjecture Almostanynon-trivialconditionsufcienttoguaranteeagraphishamiltonianisalsosucienttoguaranteeagraphis pancyclicwith,possibly,asmallnumberofexceptionalgraphs. Thismeta-conjecturehasprovidedadditionalimpetusanddirectiontothestudy ofsucientconditionstoguaranteeagraphispancyclic.In2006,Flandrinetal.[31] extendeda1974resultofErd}os[20]toshowthattheChvatal-Erd}osconditiongiven inTheorem2.9alsoappliedtopancyclicity,providingfurthersupportforBondy's meta-conjecture. Theorem2.17. Let G bea k -connectedgraphwithindependencenumber .If k and G isofsucientlylargeorder 2 ,then G ispancyclic. 2 Heretheorderisatleast2 R ; +1where R ; +1istheRamseynumbersuchthat 12

PAGE 23

Thesituation,however,issomewhatdierentforforbiddensubgraphconditions likethosegiveninTheorem2.11.OnereasonforthisdierenceisthatwhilehamiltonicityisstableunderRyjacek'sclosure,pancyclicityisnot.In[24],Faudreeand Gouldcharacterizedthepairsofforbiddensubgraphsthatimplya2-connectedgraph ispancyclic. Theorem2.18. Let X and Y beconnectedgraphssuchthat X;Y 6 = P 3 .Every2connected f X;Y g -freegraphoforder n 10 ispancyclicifandonlyif X istheclaw and Y isaninducedsubgraphofoneof f N ; 0 ; 0 ;P 6 g seeFigure2.4 N ; 0 ; 0 P 6 Figure2.4:Anygraphthatis2-connected,claw-freeanddoesnot containanyofthesegraphsasaninducedsubgraphispancyclic. NotethatthisfamilyofgraphsissmallerthanthefamilygiveninTheorem2.11 andtheonlynetisaninducedsubgraphofboth N ; 1 ; 0and N ; 0 ; 0.Consequently,therearemany2-connectedgraphsthatmeettheforbiddensubgraphconditionforhamiltonicitybutnotforpancyclicity.InChapters3,4,and5wewilltake acloserlookathowforbiddensubgraphconditionscompareforhamiltonicityand pancyclicity. 2.32-Factors A 2-factor ofagraph G isa2-regularspanningsubgraphof G .Inparticular, ahamiltoniancycleisa2-factor,soeveryhamiltoniangraphhasa2-factor.While anyred/blueedge-coloredcompletegraphon R ; +1verticeshaseitheraredcopyof K 4 or abluecopyof K +1 13

PAGE 24

thequestionofdeterminingifagraphhasa2-factorisnotNP-completesee[8], itmakessensetoinvestigatesucientconditionstoguaranteethatagraphhasa 2-factor. TheconditiongiveninTheorem2.5cannotberelaxed,ascanbeseenfrom K r;r +1 whichdoesnotcontaina2-factor.Thissamesharpnessexampleshowsthat theconditioninTheorem2.9cannotberelaxedas K r;r +1 is r -connected,buthas anindependentsetofsize r +1.Faudreeetal.[21]foundthefollowingsucient conditionbasedonforbiddensubgraphs. Theorem2.19. Let X and Y beconnectedgraphssuchthat X;Y 6 = P 3 .Every2connected f X;Y g -freegraphoforder n 10 hasa2-factorifandonlyif X istheclaw and Y isaninducedsubgraphofoneof f N ; 1 ; 1 ;N ; 1 ; 0 ;P 7 g seeFigure2.5 or X = K 1 ; 4 and Y = P 4 N ; 1 ; 1 N ; 0 ; 0 P 7 Figure2.5:Anygraphthatis2-connected,claw-freeanddoesnot containanyofthesegraphsasaninducedsubgraphcontainsa2factor. EgawaandOta[19]combinedaforbiddensubgraphconditionwithaminimum degreeconditiontoshowthefollowing. Theorem2.20. Everyclaw-freegraphwithminimumdegreeatleast4hasa2-factor. 14

PAGE 25

2.42-Factorswith k k k components Ahamiltoniancyclecanbeviewedasa2-factorwithexactlyonecomponent. Thisperspectivehasledtotheextensionofthe2-factorproblemtodetermineifa graphhasa2-factorcomposedof k components.In[6],Brandtetal.provedthe following. Theorem2.21. If k 1 isanintegerand G isagraphoforder n 4 k suchthat G n 2 ,then G containsa2-factorwithexactly k cycles. Infact,itwasshownthattheweakerOre-typedegreecondition 2 G n suces inplaceofthegivenassumptionontheminimumdegree.Thus,Theorems2.5and2.6 canbeextendedtondconditionssucienttoguaranteea2-factorwithexactly k components.KanekoandYoshimotoextendedTheorem2.9inthefollowingway[46]. Theorem2.22. Let G bea k -connectedgraphoforder n 6 .If k 4 and G G ,then G hasa2-factorwithexactlytwocomponents. Theproblemofndinga2-factorwithaconstrainednumberofcomponentsin claw-freegraphshasalsobeenconsidered.Yoshimoto[68]showedthefollowing. Theorem2.23. If G isaclaw-freegraphon n verticeswithminimumdegree 4 withnomaximalcliqueconsistingoftwovertices,then G hasa2-factorwithatmost n )]TJ/F18 7.9701 Tf 6.586 0 Td [(1 4 components. Hefurthershowedthatforinnitelymany n andevery 4,thereisaclawfreegraphon n verticeswithminimumdegree inwhichevery2-factorcontains n components.Let f 2 G denotedtheminimumnumberofcomponentsina2-factorof G .Then,for =4,thisfamily G i ofgraphshaslim j V G i j!1 f 2 G i j V G i j = 5 18 Broersmaetal.[9]improvedaresultofFaudreeetal.[22]byshowingthefollowing. 15

PAGE 26

Theorem2.24. Aclaw-freegraph G on n verticeswithminimumdegree 5 hasa 2-factorwithatmost n )]TJ/F18 7.9701 Tf 6.587 0 Td [(3 )]TJ/F18 7.9701 Tf 6.587 0 Td [(1 components.Furthermore,aclaw-freegraph G on n vertices withminimumdegree =4 hasa2-factorwithatmost n )]TJ/F15 11.9552 Tf 11.955 0 Td [(14 = 18 components. For =4,thisresultisessentiallybestpossibleinlightofthefamilyproduced byYoshimoto.InChapter6westudysucientconditionsthatensureahamiltonian graphhasa2-factorwithexactly k cycles. 16

PAGE 27

3.ForbiddenSubgraphsforPancyclicity Throughouttheremainderofthisdocument,wewillassumethatallcycles C haveaninherentclockwiseorientation.Forsomevertex v on C wewilldenotethe rst,second,and i th predecessorof v as v )]TJ/F15 11.9552 Tf 7.085 -4.338 Td [(, v \000 ,and v )]TJ/F21 7.9701 Tf 6.586 0 Td [(i respectively.Similarlywe denotetherst,second,and i th successorof v as v + v ++ ,and v + i respectively.We let xCy denotethepath xx + :::y and xC )]TJ/F20 11.9552 Tf 7.084 -4.338 Td [(y denotethepath xx )]TJ/F20 11.9552 Tf 9.078 -4.338 Td [(:::y .Also, xCyx denotesthecycleformedbythepath xCy alongwiththeedge xy .Further,let[ u;v ] C denotethesetofverticeson uCv ,andlet u;v C denotethesetofverticeson u + Cv )]TJ/F15 11.9552 Tf 7.084 -4.339 Td [(. Theintervals u;v ] C and[ u;v C aredenedsimilarly. InChapters3,4,and5wearespecicallyinterestedinthepancyclicityofhighly connectedclaw-freegraphs.Fewerresultsofthistypecanbefoundintheliterature thanresultsonhamiltonicity,inpartbecauseithasbeenshowninmanycases[60,61] thatclosuretechniquessuchasthosein[59]donotapplytopancyclicity. Theorem2.18gaveacharacterizationofallpairsofforbiddensubgraphsguarantee alargeenough K 1 ; 3 -freegraphispancyclic.For k 3,weareinterestedinlookingat pairsofforbiddensubgraphsthatguaranteea k -connectedgraphispancyclic.In[18], Duus,Gould,andJacobsonshowedthat2-connected, f K 1 ; 3 ;N ; 1 ; 1 g -freegraphs arehamiltonian.Shepherd[65]extendedthisbyshowingthefollowing. Theorem3.1 Shepherd[65] Every3-connected, f K 1 ; 3 ;N ; 1 ; 1 g -freegraphis pancyclic. Gould,Luczak,andPfender[41]obtainedthefollowingcharacterizationofforbiddenpairsofsubgraphsthatimplypancyclicityin3-connectedgraphs.Let L denote thegraphobtainedbyconnectingtwodisjointtriangleswithasingleedge.See Figure3.1 Theorem3.2 Gould,Luczak,Pfender[41] Let X and Y beconnectedgraphsonat leastthreevertices.Ifneither X nor Y is P 3 and Y isnot K 1 ; 3 ,thenevery3-connected 17

PAGE 28

N ; 1 ; 1 N ; 2 ; 0 N ; 1 ; 0 N ; 0 ; 0 L P 7 Figure3.1:Anygraphthatis3-connected,claw-freeanddoesnot containanyofthesegraphsasaninducedsubgraphispancyclic. f X;Y g -freegraph G ispancyclicifandonlyif X = K 1 ; 3 and Y isasubgraphofone ofthegraphsinthefamily F = f P 7 ; L ;N ; 0 ; 0 ;N ; 1 ; 0 ;N ; 2 ; 0 ;N ; 1 ; 1 g : 3.14-connectedGraphs MotivatedbytheMatthews-SumnerConjectureandTheorem3.2,Gouldposed thefollowingproblematthe2010SIAMDiscreteMathmeetinginAustin,TX. Problem3.3. Characterizethepairsofforbiddensubgraphsthatimplya4-connected graphispancyclic. InSection3.2weprovethefollowingwhichlimitswhatthepossiblepairsare. Theorem3.4. Let X and Y beconnectedgraphswithatleastthreeedgessuchthat every4-connected f X;Y g -freegraphispancyclic.Then,withoutlossofgenerality, X iseither K 1 ; 3 or K 1 ; 4 ,and Y isaninducedsubgraphofoneof P 9 ,L,orthegeneralized net N i;j;k with i + j + k =6 Wefurthershowthatwhen X = K 1 ; 3 ,eachofthesepairsdoesappearinthe characterizationbyshowingthefollowing[12]. Theorem3.5. Let Y beaconnectedgraphwithatleastthreeedges.Every4connected f K 1 ; 3 ;Y g -freegraphispancyclicifandonlyif Y isaninducedsubgraphof oneof P 9 ,L,orthegeneralizednet N i;j;k with i + j + k =6 18

PAGE 29

InChapter4,weshowthefollowingprogresstowardTheorem3.5thatappears in[30]. Theorem3.6. If G isa4-connected f K 1 ; 3 ;P 10 g -freegraph,theneither G ispancyclicor G isthelinegraphofthePetersengraph.Consequently,every4-connected, f K 1 ; 3 ;P 9 g -freegraphispancyclic. ThelinegraphofthePetersengraphis4-connected,claw-free,andcontainsno cycleoflength4see L P inFigure3.2.NotingthatinTheorem3.2,allgeneralized netsoftheform N i;j; 0with i + j =4areinthefamily F ,Ferrara,Gould,Gehrke, Magnant,andPowell[29]showedthefollowing. Theorem3.7. Every4-connected f K 1 ; 3 ;N i;j; 0 g -freegraphwith i + j =6 ispancyclic.Thisresultisbestpossible,inthatthelinegraphofthePetersengraphis N i;j; 0 -freeforall i;j 0 with i + j =7 InChapter5,wewillshowthatevery4-connected f K 1 ; 3 ;N ; 2 ; 2 g -freegraphis pancyclicwhichappearsin[12]aspartoftheproofofthefollowingtheorem. Theorem3.8. Every4-connected f K 1 ; 3 ;N g -freegraph,where N isoneof N ; 2 ; 2 N ; 2 ; 1 ,or N ; 1 ; 1 ,ispancyclic. Theorem3.5followsfromTheorems3.6,3.7,3.7,and3.4[12]. 3.2ProofofTheorem3.4 Throughoutthissection,wewillassumethat X;Y areconnectedgraphswithat leastthreeedgessuchthatevery4-connected, f X;Y g -freegraphispancyclic. Lemma3.9. Let X;Y beconnectedgraphswithatleastthreeedges.Ifeach4connected, f X;Y g -freegraphispancyclic,thenwithoutlossofgenerality, X 2 f K 1 ; 3 ;K 1 ; 4 g 19

PAGE 30

L S K 5 L P K 4 ; 4 G 1 G 2 K n )]TJ/F18 7.9701 Tf 6.586 0 Td [(5 Figure3.2:Some4-connectedgraphsthatarenotpancyclic Proof: Notethat L P G 1 G 2 ,and K 4 ; 4 seeFigure3.2areeach4-connected andarenotpancyclicas L P and G 1 donotcontain C 4 G 2 isnothomailtonian, and K 4 ; 4 doesnotcontain C 3 .Inaddition, L P is K 1 ; 3 K 1 ; 4 -free. Supposeonthecontrarythat X;Y= 2f K 1 ; 3 ;K 1 ; 4 g .As K 4 ; 4 isnotpancyclic,we mayconcludewithoutlossofgeneralitythat X isaninducedsubgraphof K 4 ; 4 .As X= 2f P 3 ;K 1 ; 3 ;K 1 ; 4 g and X isconnected, X mustcontainaninducedcopyof C 4 As G 1 doesnotcontain C 4 ,itmustcontain Y asaninducedsubgraph.Therefore, Y musthavegirthatleast5andmaximumdegree4.Furthermore, G 2 is C 4 -freeso that Y mustalsobeaninducedsubgraphof G 2 .However,theonlyinducedsubgraphs of G 2 withgirthatleast5andmaximumdegree 4are K 1 ; 3 and K 1 ; 4 .So, Y mustcontainaninduced K 1 ; 3 or K 1 ; 4 Lastly, L P isalso C 4 -freesothat Y mustbeaninducedsubgraphof L P However,neither K 1 ; 3 nor K 1 ; 4 isaninducedsubgraphof L P ,thenalcontradiction necessarytoestablishthelemma. 20

PAGE 31

Intheremainderofthissection,wewillassumethat X 2f K 1 ; 3 ;K 1 ; 4 g .To completetheproofofTheorem3.4,wemustcharacterizethepossibilitiesfor Y First,foravertex v ina4-connectedgraph H ,wedenea disjoint4-splitat v tobe thegraph H 0 obtainedfrom H byreplacing v withtwoadjacentvertices, x and y andaddingedgessuchthat N H 0 x [ N H 0 y = N H v [f x;y g N H 0 x N H 0 y = ; andboth deg H 0 x 4and deg H 0 y 4.WeusethefollowinglemmaduetoWest concerningdisjoint4-splits[67]. Lemma3.10. If H isa4-connectedgraphwithavertex v ofdegreeatleast6,then thegraph H 0 obtainedfrom H byadisjoint4-splitat v is4-connected. Proof: Let S 0 beaminimumcutsetof H 0 ,andlet x and y betheverticesin H 0 thatreplacedthevertex v in H .If x and y arebothin S 0 ,then S = S 0 )-222(f x;y g [f v g isacut-setof H ofsize j S 0 j)]TJ/F15 11.9552 Tf 20.245 0 Td [(1,thus j S j 5.Thereforewemayassumethat f x;y g)]TJ/F20 11.9552 Tf 17.92 0 Td [(S 0 6 = ; .If x or y isacomponentof H 0 )]TJ/F20 11.9552 Tf 10.62 0 Td [(S 0 ,then S 0 N H 0 y or S 0 N H 0 x andthus j S 0 j 4.Similarly,if xy isacomponentof H 0 )]TJ/F20 11.9552 Tf 12.163 0 Td [(S 0 ,then N H v S 0 and thus j S 0 j 6.If f x;y g)]TJ/F20 11.9552 Tf 21.238 0 Td [(S 0 = ; ,let S = S 0 ,otherwiselet S = S 0 )-222(f x;y g [f v g Now, H )]TJ/F20 11.9552 Tf 12.359 0 Td [(S isdisconnectedas,foranypathin H )]TJ/F20 11.9552 Tf 12.359 0 Td [(S replacingthevertex v with theedge xy givesapathin H 0 )]TJ/F20 11.9552 Tf 11.481 0 Td [(S 0 withthesameendvertices.Thus,since j S j = j S 0 j and j S j 4as H is4-connecte, j S 0 j 4so H 0 is4-connected. WealsousethefollowingresultofMader[51]see[34]. Lemma3.11. If G isaconnectedvertextransitivegraph,thentheedge-connectivity of G isequaltoitnecessarilyregulardegree. Finallw,wealsomakeuseofthefollowingfamilyofgraphsdevelopedbyLubotsky, Phillips,andSarnak[49]. Theorem3.12. Forinnitelymany d andall n ,thereexistsaconnected, d -regular, vertex-transitivegraphonatleast n verticesthathasarbitrarilylargegirth.Inaddition,thesegraphsexistfor d = p +1 ,where p isanoddprime. 21

PAGE 32

Thesegraphs,oftencalled`Ramanujangraphs,'wereusedbyBrandt,Favaron, andRyjacek[7]toshowthatforeach k 2,thereexistsa k -connected,claw-free graphthatisnotpancyclic.Wewilluseaverysimilarapproachtoprovethefollowing lemma,whichtogetherwithLemma3.9,impliesTheorem3.4. Lemma3.13. Thereexistsa4-connected,claw-free,non-pancyclicgraph G suchthat if Y isaninducedsubgraphof L P L S K 5 ,and G ,then Y isaninducedsubgraph of P 9 ,L,or N i;j;k ,with i + j + k =6 Proof: Let H beaconnected,4-regular,vertex-transitivegraphwithgirth g 9,asguaranteedbyTheorem3.12.ByLemma3.11,since H isconnected,4regular,andvertex-transitive, H isalso4-edgeconnected.Itfollowsthat L H isa 6-regular,4-connected,claw-freegraph.Notethateachvertex x of H isrepresented byagraph G x = K 4 in L H .Furthereachedge xy 2 E H correspondstoavertex v 2 L H thatliesinexactlytwo K 4 's. Let H 0 beobtainedfrom L H byperformingadisjoint4-splitoneachvertexas follows.Let v 2 V L H withneighbors f x 1 ;x 2 ;x 3 ;y 1 ;y 2 ;y 3 g ,wherethe x i 'sand y i 'sareindistinct K 4 's.Delete v andreplaceitwithadjacentvertices x;y suchthat N x = f y;x 1 ;x 2 ;x 3 g and N y = f x;y 1 ;y 2 ;y 3 g .ByLemma3.10, H 0 is4-connected. Eachvertex x 2 V H 0 hasaneighborhoodconsistingofa K 3 anda K 1 ,so H 0 is claw-free.Notethat H 0 contains3-cyclesand4-cycles,butdoesnotcontaincycles oflength t for5 t< 2 g ,andthus,since g 9,thegraph H 0 doesnotcontaina 17-cycle. Each G x in L H correspondstoagraphisomorphicto K 4 in H 0 whichwewill alsorefertoas G x .Foragiven G x in H 0 subdivideeachedgeof G x exactlytwice. Forthesakeofclarity,colorthesenewverticeswhite,andcolortheoriginalvertices of H 0 ,black,andthenaddedgessothatthe12newwhiteverticesinduceaclique. Let e G x bethisnewsubgraphoforder16,andrepeatthisforeach G v in H 0 toobtain thegraph G 22

PAGE 33

L H H 0 G v xy 2 E H x 1 x 2 x 3 y 1 y 2 y 3 x y x 1 x 2 x 3 y 1 y 2 y 3 K 12 x x 1 x 2 x 3 Figure3.3:Formingthegraph G Weclaimrstthat G isclaw-free.Indeed,ifablackvertexisthecenterofaclaw, thenatleasttwooftheotherverticesintheclawmustbewhiteverticeslyingina common e G v .Similarly,eachwhitevertexhasonlyoneblackneighborandallofits whiteneighborslieinasingle e G v .Toestablishthat G is4-connected,assume S isa minimumcut-setin G withatmostthreevertices.If S hasanywhitevertices,then itmustcontainthreewhitevertices,asremovingatmosttwowhiteverticeswillnot disconnectany e G v ,letalone G .However,deletingthreewhiteverticesfromasingle e G v cannotdisconnect G ,as e G v itselfisconnectedunlessallthreeofthesevertices haveacommonblackneighbor v 0 2 e G v .As v 0 hasdegree4, v 0 hasanotherneighbor v "thatisinthesamecomponentof G )]TJ/F20 11.9552 Tf 10.706 0 Td [(S as v 0 .Butthen,since S isina K 12 ,theset f v 0 g isasmallercut-setthan S .So,wemayassume S containsonlyblackvertices. Thisdirectlycorrespondstodeletingverticesin H 0 ,whichis4-connected.Thus,in allcases, G )]TJ/F20 11.9552 Tf 11.955 0 Td [(S isconnected. Wealsoclaimthat G isnotpancyclic.Indeed, G containscyclesoflength 3 ;:::; 16.However,anycycleoflength17mustcontainverticesfromdistinct e G v 'sin G .Ifweignoreallwhiteverticesofourcycle,thiscorrespondstoacyclein H 0 using 23

PAGE 34

distinctverticesfromdistinct G v 's.Asthesmallestcyclesin H 0 areoflength3,4and 2 g 18,ourcorrespondingcyclemusthavelengthatleast2 g 18in H 0 ,andthus haslengthatleast18in G .Consequently, G hasnocycleoflength17,andso,isnot pancyclic. Lastly,let Y beaninducedsubgraphof L P L S K 5 ,and G .Weshowthat Y isaninducedsubgraphof P 9 L ,or N i;j;k with i + j + k =6,tocompletethe proof. Tobegin,weclaimthat Y iseitheratreeorhasgirth3.Supposeonthecontrary that Y isnotatreeandhasgirthatleast4.Since L P and L S K 5 are C 4 and C 5 -free,respectively, Y musthavegirthatleast6.Inaddition, L S K 5 impliesthat Y hasgirthatmost10,elseitcontainsa3-cycle.However,if C isacyclein G of lengthatmost16,then G [ V C ]containsa3-cycle,acontradiction. Supposenowthat Y isnotatree.If Y hastwodistinctcycles,thenbytheabove argument,wemayassumethat Y hasatleasttwodistinct3-cycles.Considering L P ,notwo3-cyclescansharetwovertices,andconsidering L S K 5 ,notwo3cyclescanshareexactlyonevertex.Thus,everypairof3-cyclesmustbejoinedbya path.Byconsidering L P ,itisclearthatiftwo3-cyclesarejoinedbyapath,they arejoinedbyasingleedge.Thatis, L isaninducedsubgraphof Y .Whilethere aremanyinducedsubgraphsof L in G ,itiseasytoseethatif Y 6 = L ,then Y must containa4-cycle,acontradictionto Y L P .So,unless Y = L Y cannotcontain twodistinctcycles. Thus,if Y isnot L and Y hasacycle,itmustbea3-cycle,and Y mustbe unicyclic.Thatis, Y isageneralizednet.Notethat L P is N i;j;k -freewhen i;j 1and i + j + k =7.Thus, Y mustbeaninducedsubgraphof N i;j;k where i + j + k =6. Lastly,if Y isatree,thenas L P is K 1 ; 3 -free, Y mustbeapath,andby[30], Y mustbeaninducedsubgraphof P 9 .Thiscompletestheproof. 24

PAGE 35

4.Pancyclicityof f K 1 ; 3 ;P 10 g f K 1 ; 3 ;P 10 g f K 1 ; 3 ;P 10 g -freegraphs Inthischapter,weproveTheorem3.6thatevery4-connected f K 1 ; 3 ;P 10 g -free graphispancyclicexceptthelinegraphofthePetersengraph.Wedothisbyrst showingthateach4-connected,claw-free, P 10 -freegraph G containsacycleofeach lengthfrom10through j V G j .Wethenshowthatthesegraphs,excepttheline graphofthePetersengraph,havecyclesoflength3through9. 4.1LongCycles Let G bea4-connected,claw-free, P 10 -freegraphoforder n .Wewillrstshow that G containscyclesofalllengthfrom10to n ,followingcloselythetechniqueused byGould,Luczak,andPfenderin[41].Tothisend,thefollowinglemmaofGould, Luczak,andPfender[41]willbevaluable.A hop isachordinacyclethatjoinssome vertex v to v ++ Lemma4.1 Gould,Luczak,Pfender[41] Let G beaclaw-freegraphwithminimum degreeatleast 3 ,let C beacycleoflength t 5 withouthops,andlet X betheset ofverticesin C thatarenotonanychordof C .Ifsomechord xy of C satises j X C x;y j 2 ,then G containscyclesoflengths t )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 and t )]TJ/F15 11.9552 Tf 11.955 0 Td [(2 WeuseLemma4.1toprovethefollowing. Lemma4.2. Let G bea4-connected,claw-freegraphoforder n andsupposethat G containsacycleoflength t 5 withatleastonechord.If G containsnocycleof length t )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 then G containsaninducedcopyof P 10 Proof: Let C beacycleoflength t in G withatleastonechordandsuppose that G containsno t )]TJ/F15 11.9552 Tf 12.881 0 Td [(1-cycle.Let X bethesetofverticesof C thatarenot endpointsofchordsof C .Let xy beachordof C suchthat j C x;y X j isminimized and xy istheonlychordthatjoinsapairofverticesin C [ x;y ].If x + y + isanedge foreverysuchedge xy ,thenforanysuch xy ,everyvertexin C x;y isnotin X andthusLemma4.1givesa t )]TJ/F15 11.9552 Tf 12.498 0 Td [(1-cycle.Therefore,wemayassumethat xy was 25

PAGE 36

chosensothat x + y + = 2 E G .Since G containsno t )]TJ/F15 11.9552 Tf 11.462 0 Td [(1-cycle, C ishop-freeandby Lemma4.1, j C x;y X j 3.Webeginbyshowingthat j C x;y j 5. Assumerstthat j C x;y j =3.Byminimalityof xy ,thereareatleastthree verticesin X containedin C y;x .Let x 1 ;x 2 x 3 bethreesuchverticeslabeledwith respecttotheorientationof C .Since G is4-connected,eachvertexin X hasatleast twoneighborsnoton C .Ifavertex v in C hasaneighbor v 0 notin C ,then v 0 isalso adjacentto v )]TJ/F15 11.9552 Tf 10.527 -4.338 Td [(or v + as G isclaw-freeand C ishop-free.A claw-extension of C isthe extensionof C byreplacing v )]TJ/F20 11.9552 Tf 7.084 -4.338 Td [(vv + with v )]TJ/F20 11.9552 Tf 7.085 -4.338 Td [(vv 0 v + or v )]TJ/F20 11.9552 Tf 7.085 -4.338 Td [(v 0 vv + .Thusthe t )]TJ/F15 11.9552 Tf 12.07 0 Td [(3-cycle xyCx canbeextendedtoa t )]TJ/F15 11.9552 Tf 11.956 0 Td [(1-cycleviaclaw-extensionsat x 1 and x 3 Nowassumethat j C x;y j =4.Weshowthatallfourverticesin C x;y arealso elementsof X .Supposeoneofthemisnot;callit p .Byminimalityof xy ,weconclude that p hasaneighbor q in C y;x .Pick q suchthat j C y + ;q j isminimized.Because G isclaw-freeand C ishop-free, pq + 2 E G .Let x 1 beavertexin C y;x X ; notethat x 1 existsbecause j C y;x X j 3byassumption,andalso x 1 isnot q or q + .Alsolet u and v betwoneighborsof x 1 thatarenotin C .Notethatboth u and v haveaneighborin f x + 1 ;x )]TJ/F18 7.9701 Tf 0 -7.879 Td [(1 g .If u and v arebothadjacentto x + 1 andnot adjacentto x )]TJ/F18 7.9701 Tf 0 -7.879 Td [(1 similarly,adjacentto x )]TJ/F18 7.9701 Tf 0 -7.879 Td [(1 andnotadjacentto x + 1 ,then u and v areadjacent.Otherwise,itispossibletopickdistinctneighborsfor x + 1 and x )]TJ/F18 7.9701 Tf 0 -7.879 Td [(1 from f u;v g ;withoutlossofgeneralityweassumethat ux + 1 ;vx )]TJ/F18 7.9701 Tf 0 -7.88 Td [(1 2 E G .Thusitispossible toreplace C [ x )]TJ/F18 7.9701 Tf 0 -7.88 Td [(1 ;x + 1 ]with x )]TJ/F18 7.9701 Tf 0 -7.88 Td [(1 uvx 1 x + 1 x )]TJ/F18 7.9701 Tf 0 -7.88 Td [(1 x 1 uvx + 1 ,or x )]TJ/F18 7.9701 Tf 0 -7.88 Td [(1 vx 1 ux + 1 ,andreplace qq + with qpq + ,therebyextendingthe t )]TJ/F15 11.9552 Tf 11.733 0 Td [(4-cycle xyCx toa t )]TJ/F15 11.9552 Tf 11.733 0 Td [(1-cycle.Thuseveryvertex in C x;y isalsoin X Bytheminimalityof xy ,thereareatleastfourverticesin C y;x X ;let X 0 = f x 1 ;x 2 ;x 3 ;x 4 g beasetoffoursuchverticeslabeledwithrespecttotheorientation of C .Wehaveshownthatitispossibletoaddtwoverticesnotin C to C [ x )]TJ/F21 7.9701 Tf 0 -8.012 Td [(i x i x + i ] forany i 2 [4].Thus,if j N X 0 )]TJ/F20 11.9552 Tf 12.843 0 Td [(C j 3,thenwecanextendthe t )]TJ/F15 11.9552 Tf 12.843 0 Td [(4-cycle xyCx toa t )]TJ/F15 11.9552 Tf 11.892 0 Td [(1-cycle.Henceweassumethatthereareexactlytwovertices, u and 26

PAGE 37

v ,in N X 0 )]TJ/F20 11.9552 Tf 12.779 0 Td [(C andthateachvertexin X 0 isadjacenttoboth u and v .Ifany threeverticesin X 0 arepairwisenon-consecutiveon C ,thenthereisaclawcentered at u .Also,ifthereareexactlytwoverticeson C between x i and x j in X 0 ,then G containsthe t )]TJ/F15 11.9552 Tf 12.539 0 Td [(1-cycle x i ux j Cx i assuming i
PAGE 38

than yx )]TJ/F15 11.9552 Tf 11.739 -4.338 Td [(joining C [ x + ;y ]and C [ x )]TJ/F18 7.9701 Tf 6.586 0 Td [( )]TJ/F21 7.9701 Tf 6.586 0 Td [(k ;x )]TJ/F15 11.9552 Tf 7.084 -4.338 Td [(],thenthepathisinduced.Let wz be suchachordwith w 2 C [ x )]TJ/F18 7.9701 Tf 6.587 0 Td [( )]TJ/F21 7.9701 Tf 6.587 0 Td [(k ;x )]TJ/F15 11.9552 Tf 7.084 -4.338 Td [(]and z 2 C [ x + ;y ].If z 2f y )]TJ/F20 11.9552 Tf 7.084 -4.338 Td [(;y g ,then G containsacycleon t )]TJ/F15 11.9552 Tf 11.016 0 Td [(1or t )]TJ/F15 11.9552 Tf 11.016 0 Td [(2verticesin V C thatcontainsthepath xCy )]TJ/F15 11.9552 Tf 7.085 -4.338 Td [(.If necessary,suchacyclecanbeextendedtoa t )]TJ/F15 11.9552 Tf 11.653 0 Td [(1-cycleviaaclaw-extension.Thus z 2 C [ x + ;y \000 ].Thecombinationoftheminimalityof xy andthefactthat z 6 = y )]TJ/F15 11.9552 Tf -424.915 -28.319 Td [(thenimpliesthat w 6 = x )]TJ/F15 11.9552 Tf 7.084 -4.339 Td [(. Wenowchoose wz sothat j C w;z j isminimized.Theminimalityof wz implies that w )]TJ/F20 11.9552 Tf 7.084 -4.338 Td [(z and wz + areedges.Let A = C x;z B = C z + ;y ,and D = C w;x )]TJ/F15 11.9552 Tf 7.085 -4.338 Td [(. seeFigure4.2Notethat j D j 2, j A j + j B j = k )]TJ/F15 11.9552 Tf 12.75 0 Td [(2,and j A j + j B j + j D j 5. Considerthetwocycles C 0 = wz + C )]TJ/F20 11.9552 Tf 7.084 -4.338 Td [(x )]TJ/F20 11.9552 Tf 7.085 -4.338 Td [(yCw and C 00 = wzCyxx )]TJ/F20 11.9552 Tf 7.085 -4.338 Td [(y + Cw .Observe that C 0 containsnoverticesin B [ D and C 00 containsnoverticesin A [ D ,thus neitherofthesecyclescontains t vertices. w )]TJET1 0 0 1 144.63 247.766 cmQ 1 0 0 1 293.494 -195.408 cmQ Q q q 1 0 0 1 -271.432 221.543 cm1.0 0.0 0.0 1.0 0.0 0.0 cm q 0 G 0 g 1 0 0 1 -166.692 -273.901 cmBT/F20 11.9552 Tf 166.692 273.901 Td [(w w + z )]TJET1 0 0 1 312.346 375.417 cmQ 1 0 0 1 125.778 -323.059 cmQ Q q q 1 0 0 1 -93.225 334.208 cm1.0 0.0 0.0 1.0 0.0 0.0 cm q 0 G 0 g 1 0 0 1 -344.899 -386.566 cmBT/F20 11.9552 Tf 344.899 386.566 Td [(z z + z ++ x \000 x )]TJET1 0 0 1 231.271 333.388 cmQ 1 0 0 1 206.853 -281.03 cmQ Q q q 1 0 0 1 -177.656 299.377 cm1.0 0.0 0.0 1.0 0.0 0.0 cm q 0 G 0 g 1 0 0 1 -260.468 -351.735 cmBT/F20 11.9552 Tf 260.468 351.735 Td [(x x + y )]TJET1 0 0 1 431.514 397.605 cmQ 1 0 0 1 6.61 -345.247 cmQ Q q q 1 0 0 1 27.32 345.92 cm1.0 0.0 0.0 1.0 0.0 0.0 cm q 0 G 0 g 1 0 0 1 -465.444 -398.278 cmBT/F20 11.9552 Tf 465.444 398.278 Td [(y y + x )]TJ/F18 7.9701 Tf 6.586 0 Td [( )]TJ/F21 7.9701 Tf 6.586 0 Td [(k A B D Figure4.2:Thesets A B ,and D ina t -cycle. If j D j =2,then k =5and A [ B X .Furthermore,either j A j =1or j B j =1 andeither C 0 or C 00 isa t )]TJ/F15 11.9552 Tf 11.431 0 Td [(3-cycle.Suchacyclecanbeextendedtoa t )]TJ/F15 11.9552 Tf 11.431 0 Td [(1-cycle usingclaw-extensions.If j D j 1,thenbytheminimalityof xy thereareatleast 28

PAGE 39

threeverticesin C y + ;x )]TJ/F15 11.9552 Tf 7.085 -4.338 Td [( X ,atleasttwoofwhichliein C y + ;w .Thusif C 0 or C 00 haslengthatleast t )]TJ/F15 11.9552 Tf 11.724 0 Td [(3wecanextendtoa t )]TJ/F15 11.9552 Tf 11.724 0 Td [(1-cycleusingclaw-extensions. Therefore G containsa t )]TJ/F15 11.9552 Tf 12.232 0 Td [(1-cycleunless j A j + j D j 4and j B j + j D j 4,which togetherwiththefactthat j A j + j B j + j D j 5yieldsacontradiction. ThefollowingresultofLuczakandPfender[50]allowsustoobtaincyclesof lengthatleast10. Theorem4.3 Luczak,Pfender[50] Every3-connected,claw-free, P 11 -freegraphis hamiltonian. Iffollowsthatevery4-connected,claw-free, P 10 -freegraph G ishamiltonian.The assumptionthat G is P 10 -freeimpliesthat G containsnoinducedcycleoflengthat least11.Therefore,byLemmas4.1and4.2, G containscyclesoflength10through j V G j 4.2ShortCycles Inthissectionweshowthata4-connected,claw-free, P 10 -freegraph G withat leastnineverticeseithercontainscyclesoflengths3through9oristhelinegraphof thePetersengraph.Theexistenceofa3-cyclefollowsimmediatelyfromthefactthat G isclaw-free.For4-and5-cyclesweusesimilarargumentsbasedonlongestinduced paths.For6-,7-,and8-cyclesweuseanargumentbasedontheneighborhoodsof verticesinsmallercycles.Finally,theexistenceofa9-cyclefollowsfromtheexistence ofa10-cycle. Webeginbyshowingthat G eithercontainsa4-cycleoristhelinegraphofthe Petersengraph.Let Z t = N t; 0 ; 0.Weusethefollowing,whichisanimmediate consequenceofTheorem3.7. Theorem4.4. Every4-connected,claw-free, Z 5 -freegraphispancyclic. Webeginbyestablishingthestructureoftheneighborhoodofanyvertexofa 4-connected,claw-freegraphwithno C 4 29

PAGE 40

Claim4.5. If G is4-connected,claw-free,anddoesnotcontain C 4 ,then G is4regularandforall v 2 V G N v induces 2 K 2 Proof: Supposethat G doesnotcontaina4-cycle.Since G isclaw-free,the neighborhoodofanyvertexiseitherconnectedortwocliques.As G hasminimum degree4,iftheneighborhoodisconnected,thentheneighborhoodcontainsapath oforder3,yieldinga4-cycle.Thustheneighborhoodofanyvertexistwocliques.If anyvertexhasdegreeatleast5,thenoneofthecliqueshasatleastthreevertices, yieldinga4-cycle.Thus G is4-regularandtheclosedneighborhoodofeachvertex inducestwotrianglesidentiedatthatvertex. Assumegoingforwardthat C 4 6 G sothat G is4-regular. Lemma4.6. If G isa 4 -connected,claw-free, P 10 -freegraph,theneither G isthe linegraphofthePetersengraphor G containsa 4 -cycle. Proof: Weconsideralongestinducedpath P in G ;let v 1 ;:::;v t bethevertices of P labeledinorder.As G is4-regular, v 1 hasexactlythreeneighborsthatarenot in P ,callthesevertices x 1 x 2 ,and x 3 .Because v 1 liesintwotriangles,wemay assumewithoutlossofgeneralitythat x 3 isadjacentto v 2 andthat x 1 and x 2 are adjacent.Because G doesnotcontain P t +1 asaninducedsubgraph,both x 1 and x 2 musthaveneighborsin V P )]TJ/F20 11.9552 Tf 12.539 0 Td [(v 1 .Since G doesnotcontaina4-cycle, x 1 and x 2 havenocommonneighborsbesides v 1 andarenotadjacentto v 2 or v 3 .Furthermore, aneighborof x 1 cannotbeadjacenttoaneighborof x 2 .Also,because G isclaw-free, anyvertexthatisadjacentto v i for i 2f 2 ;:::;t )]TJ/F15 11.9552 Tf 12.126 0 Td [(1 g mustalsobeadjacentto v i +1 or v i )]TJ/F18 7.9701 Tf 6.586 0 Td [(1 ByTheorem4.4,wemayassumethat G containsaninducedcopyof Z 5 ,and therefore t 7.If t =7,thenuptosymmetry x 1 isadjacentto v 4 and v 5 ,and x 2 isadjacentto v 7 .Itfollowsthatthereisavertex x 0 2 thatisadjacentto x 2 and v 7 whichmustalsohaveneighborsin V P )]TJ/F20 11.9552 Tf 11.892 0 Td [(v 7 .Theonlypossibleneighborof x 0 2 that 30

PAGE 41

doesnotcompletea4-cycleis v 3 ,andthus G containseithera4-cycleoraninduced claw. Nowassumethat t =8;therearethreecasestoconsider.If x 1 isadjacentto v 4 and v 5 and x 2 isadjacentto v 7 and v 8 ,then v 8 hastwoadditionalneighbors y 1 and y 2 ,bothofwhichhaveneighborsin V P )]TJ/F20 11.9552 Tf 12.127 0 Td [(v 8 .Because G isclaw-freeandhas no4-cycle,theseneighborslieintheset f v 4 ;v 3 ;v 2 g ;thus y 1 and y 2 haveasecond commonneighbor,yieldinga4-cycle.If x 1 isadjacentto v 4 and v 5 and x 2 isadjacent to v 8 butnot v 7 ,thenthereisavertex x 0 2 thatisadjacentto x 2 and v 8 .If x 0 2 hasno neighborin V P )]TJ/F20 11.9552 Tf 12.449 0 Td [(v 8 ,then G containstheinduced9-vertexpath x 0 2 x 2 v 1 :::v 7 ;as before,theonlypossibleneighborof x 0 2 thatdoesnotcompletea4-cycleis v 3 ,and thus G containsa4-cycleoraninducedclaw.Finally,supposethat x 1 isadjacent to v 5 and v 6 and x 2 isadjacentto v 8 .If x 3 doesnothaveadditionalneighborsin P then G containstheinducedpath x 2 v 8 :::v 2 x 3 .Theonlypossibleneighborof x 3 in V P )]TJ/F20 11.9552 Tf 11.23 0 Td [(v 1 thatdoesnotcompletea4-cycleis v 7 ,andthus G containsa4-cycleoran inducedclaw.Weconcludethatthelongestinducedpathin G containsninevertices. Both v 1 and v 9 havethreeneighborsthatdonotliein P .Let y 1 y 2 ,and y 3 be theneighborsof v 9 with y 3 adjacentto v 8 ;notethattheyarenotnecessarilydistinct from x 1 x 2 ,and x 3 theneighborsof v 1 ,asbefore.Supposethat x 1 ;x 2 ;x 3 ;y 1 ;y 2 and y 3 arealldistinct.Since x 1 and x 2 bothhaveneighborsin P ,weconcludeupto symmetrythat x 1 isadjacentto v 4 and v 5 and x 2 isadjacentto v 7 and v 8 .Likewise wemayassumethat y 1 isadjacentto v 5 and v 6 andthat y 2 isadjacentto v 2 and v 3 .Because G isclaw-freeandcontainsno4-cycle, x 3 hasnoadditionalneighbors in P .Thus x 3 v 2 v 3 v 4 x 1 x 2 v 7 v 6 y 1 v 9 isaninduced10-vertexpath.Therefore v 1 and v 9 haveacommonneighborandsince G containsno4-cycle,weconcludethattheyhave exactlyonecommonneighbor. Supposerstthat x 3 = y 3 ;thatis,thereisavertexthatisadjacentto v 1 ;v 2 ;v 8 and v 9 .Thus x 1 and x 2 cannotbeadjacentto v 1 ;v 2 ;v 3 ;v 8 ,or v 9 ,andthereforehave 31

PAGE 42

neighborsin f v 4 ;:::;v 7 g .Itthenfollowsthat G containsa4-cycleoraninduced claw.Nowsupposethat x 2 = y 2 ;thatis,thereisavertexthatisadjacentto v 1 and v 9 butnootherverticesin P .Itfollowsthattheneighborsof x 1 areapairof consecutiveverticesin f v 4 ;:::;v 7 g andtheneighborsof y 1 areapairofconsecutive verticesin f v 3 ;:::;v 6 g .Since x 1 and y 1 cannothaveacommonneighborin P such avertexcompletesa4-cycle,weconcludethat x 1 isadjacentto v 6 and v 7 orthat y 1 isadjacentto v 3 and v 4 .Assuming,withoutlossofgenerality,that x 1 isadjacent to v 6 and v 7 ,itfollowsthat x 3 hasnoneighborsin P )-227(f v 1 ;v 2 g since G isclaw-free. Thus x 2 v 9 :::v 2 x 3 isaninduced10-vertexpath. Itremainstoconsiderthecasewhenuptosymmetry x 3 = y 2 ;thatis,there isavertexthatisadjacentto v 1 v 2 ,and v 9 seeFigure4.3.Theneighborsof x 1 and x 2 arepairsofconsecutiveverticesfrom f v 4 ;:::;v 8 g ,andsince x 1 and x 2 cannot haveadjacentneighbors,wemayassumeuptosymmetrythat x 1 isadjacentto v 4 and v 5 ,and x 2 isadjacentto v 7 and v 8 .Inthiscase,sincetheneighborsof y 1 areconsecutiveverticesin f v 4 ;v 5 ;v 6 g ,weconcludethat y 1 isadjacentto v 5 and v 6 Weconsidertheneighborsof y 3 .If y 3 hastwoneighborsthatarenotin P ,then eachmusthaveneighborsin P toavoidaninduced10-vertexpath.Theneighbors oftheseverticesmustbeconsecutiveverticesfromtheset f v 2 ;v 3 ;v 4 ;v 6 ;v 7 g these aretheverticesthatdonotyethavefourneighbors.Ifoneisadjacentto v 6 and v 7 ,then G containsa4-cycle.Otherwise,theyarebothadjacentto v 3 ,whichagain yieldsa4-cycle.Weconcludethatallneighborsof y 3 arein P .Since G doesnot contain4-cyclesandtheneighborsof y 3 liein f v 2 ;v 3 ;v 4 ;v 6 ;v 7 g ,weconcludethat y 3 isadjacentto v 3 and v 4 .Finallyweconsidertheremainingneighborsof v 2 ;v 3 ;v 6 ,and v 7 .Since G isclaw-free, v 2 and v 3 haveacommonneighbor u .If u isnotadjacentto v 6 and v 7 ,then v 1 x 3 v 9 :::v 3 u isaninduced10-vertexpath.Thus u isalsoadjacentto v 6 ,and v 7 .As G is4-regular,therearenoremainingverticesand G isthelinegraph ofthePetersengraph. 32

PAGE 43

v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9 x 1 x 2 y 3 y 1 u x 3 = y 2 v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9 x 1 x 2 y 3 y 1 u x 3 Figure4.3:Thecasewhen x 3 = y 2 givesrisetothelinegraphofthe Petersengraph. Toshowtheexistenceof5-cyclesweuseanargumentsimilartotheproofof Lemma4.6.NotethatthelinegraphofthePetersengraphdoescontaina5-cycle, soitisnotanexceptionalgraphinthiscase. Lemma4.7. If G isa 4 -connected,claw-free, P 10 -freegraph,then G containsa 5 -cycle. Proof: Supposethat G doesnotcontaina5-cycle.If G containsa4-cycle,then eachvertexinthecyclehasaneighbornotinthecyclesince G is4-connected.Because G isclaw-freeandhasno5-cycle,thevertexsetofthe4-cycleinducesaclique.Let f v 1 ;:::;v t g bethevertexsetofalongestinducedpath P in G ;byTheorem4.4, t 7. Werstconsiderthecasewhen v 1 hastwoneighbors x 1 and x 2 thatareadjacentsuch that x 2 isalsoadjacentto v 2 seeFigure4.4. Since f v 1 ;v 2 ;x 1 ;x 2 g isthevertexsetofa4-cycle,itisaclique.Because G is 4-connected, v 1 hasathirdneighbornotin P ;callit x 3 .As P isalongestinduced pathand G containsno5-cycle, x 3 musthaveaneighborin f v 5 ;:::;v t g .Observethat 33

PAGE 44

v 1 v 2 v 3 v 4 v 5 v 6 v t x 1 x 2 x 3 Figure4.4:Thecasewhen v 1 hastwoadjacentneighbors x 1 and x 2 with x 2 adjacentto v 2 x 3 and x 1 similarly x 2 cannothaveneighborsin P thatarecommonoradjacent. Sinceaneighborofaninternalvertexin P mustbeadjacenttoconsecutivevertices in P ,weconcludethat x 1 and x 2 donothaveanyneighborsin V P )-173(f v 1 ;v 2 g when t =7.Furthermore,when t 2f 8 ; 9 g ,atmostoneof x 1 and x 2 canhaveneighbors in V P )-324(f v 1 ;v 2 g .Withoutlossofgenerality,assumethat x 1 hasneighborsin f v 3 ;:::;v t g .Because G doesnotcontain5-cycles,if x 1 isadjacentto v i ,then i 6. Itfollowsthattherearevepossiblewaysthat x 1 and x 3 canhaveneighborsin V P )-222(f v 1 ;v 2 g withoutcreatinginducedclawsor5-cycles: t =8and x 3 v 5 ;x 3 v 6 ;x 1 v 8 2 E G ; t =9and x 3 v 5 ;x 3 v 6 ;x 1 v 9 2 E G ; t =9and x 3 v 5 ;x 3 v 6 ;x 1 v 8 ;x 1 v 9 2 E G ; t =9and x 3 v 6 ;x 3 v 7 ;x 1 v 9 2 E G ; t =9and x 3 v 9 ;x 1 v 6 ;x 1 v 7 2 E G Inallvecases,consideraneighbor x 0 2 of x 2 ,whichexistsbecause G is4connected.If x 0 2 hasanyneighborsin P ,then G containseithera5-cycleoran inducedclaw.Therefore v t :::v 2 ;x 2 ;x 0 2 isaninducedpathon t +1vertices.We concludethatneither x 1 nor x 2 hasneighborsin V P )-222(f v 1 ;v 2 g As G is4-connected, x 1 and x 2 havedistinctneighbors x 0 1 and x 0 2 thatarenotin V P [f x 1 ;x 2 ;x 3 g .Itisclearthat f x 0 1 ;x 0 2 ;x 3 g isanindependentset,otherwise G 34

PAGE 45

containsa5-cycle.Since P isaninducedpathwiththemaximumnumberofvertices, x 0 1 ;x 0 2 and x 3 allmusthaveneighborsin P .Furthermore,theseneighborsmustbe distinct.Itfollowsthatthisisonlypossibleif t =9anduptosymmetry, x 0 1 is adjacentto v 5 and v 6 x 0 2 isadjacentto v 7 and v 8 ,and x 3 isadjacentto v 9 .However, x 3 v 9 v 8 v 7 v 6 x 0 1 x 1 v 2 v 3 v 4 isthenaninduced10-vertexpath.Weconcludethat v 1 does nothavetwoadjacentneighborsthatareadjacentto v 2 Wenowconsiderthecasewhenthecommonneighborsof v 1 and v 2 areanindependentset.Since v 1 hasatleastthreeneighborsthatarenotin P ,eachofwhich hasaneighborin P )]TJ/F20 11.9552 Tf 12.344 0 Td [(v 1 ,itisclearthat v 1 and v 2 musthaveacommonneighbor; callit x 3 .Furthermore,since G isclaw-free, v 1 hastwoneighborsnotin P thatare adjacent;againwecallthem x 1 and x 2 .Both x 1 and x 2 musthaveneighborsin P )]TJ/F20 11.9552 Tf 10.025 0 Td [(v 1 andtheseneighborscannotbein f v 2 ;v 3 ;v 4 g ,norcantheybeadjacentoratdistance 2in P .Thustherearetwocasestoconsider.Firstsupposethat x 1 and x 2 areadjacentto v t .Because G is4-connectedandclaw-free, x 1 hasanadditionalneighbor x 0 1 thatisadjacentto v 1 or v t ,completinga5-cycle.Inthesecondcase, t =9and, uptosymmetry, x 1 v 5 ;x 1 v 6 ;x 2 v 9 2 E G .Notethatinthiscase, x 3 cannothaveany additionalneighborsin P .Inparticular, x 3 isnotadjacentto v 3 becausethe4-cycle on f x 3 ;v 3 ;v 2 ;v 1 g wouldforceaclique,and P wouldnotbeinduced.Thus x 3 hasat leasttwoadditionalneighbors x 0 3 and x 00 3 thatarenotin P andwhich,byassumption, arenotadjacentto v 2 .Theonlypossibleneighborsthattheseverticescanhavein P are v 7 and v 8 ,andbecause G isclaw-freeandhasno5-cyclewemayassumethat x 0 3 doesnothaveanyneighborsin P .Therefore v 9 :::v 2 x 3 x 0 3 isaninduced10-vertex path. Thefollowingnotationisusefulfortheproofofthenextlemma.Forasetof vertices S ,let N k S = f v j min f d v;v i g = k;v i 2 S g Lemma4.8. If G isa4-connected,claw-free, P 10 -freegraph,then G containscycles oflength6,7,and8. 35

PAGE 46

Proof: ByLemma4.7, G containsa5-cycle.Let t bethelargestintegerless than8suchthat G containsa t -cyclebutno t +1-cycle,andlet C bea t -cyclein G Since G is4-connected, C hasatleastfourvertices v 1 v 2 v 3 ,and v 4 withaneighbor notin C .If v i hasaneighbor w i thatisnotin V C suchthat w i isadjacentto either v + i or v )]TJ/F21 7.9701 Tf -0.429 -8.012 Td [(i ,then G containsa t +1-cycle.Thus,since G isclaw-free,wemay assumethat v + i isadjacentto v )]TJ/F21 7.9701 Tf -0.429 -8.012 Td [(i .Usingsimilarargumentsweconcludethat G [ V C ] containsoneofthegraphsinFigure4.5asasubgraph,where v 1 v 2 v 3 ,and v 4 are theverticesincidenttothedashededges. C 5 C 6 C 7 Figure4.5:Necessarysubgraphsin G [ V C ]with v 1 v 2 v 3 ,and v 4 incidenttothedashededges. If t =5,then G [ V C ]containspathsoflength1through4joiningeachpair ofverticestakenfrom f v 1 ;:::;v 4 g .Similarly,if t 6,then G [ V C ]containspaths oflength2through t )]TJ/F15 11.9552 Tf 12.437 0 Td [(1joiningeachpairofverticestakenfrom f v 1 ;:::;v 4 g .Let P i;j beashortestpathin G [ V C ]connecting v i and v j thatdoesnotcontain v k for any k distinctfrom i and j .For i 2f 1 ; 2 ; 3 ; 4 g ,let V i = N v i N 1 V C ,andlet 36

PAGE 47

V 0 i = N 2 v i N 2 V C .Weconcludethatfor1 i
PAGE 48

V 00 1 V 00 2 and x ; 4 2 V 00 3 V 00 4 .Since G isclaw-free, x ; 2 x ; 4 = 2 E G ,implyingthat V 1 V 0 1 x ; 2 V 0 2 V 2 v 2 P ; 3 v 3 V 3 V 0 3 x ; 4 isaninducedpathonatleast10vertices. Nowsupposethattherearevertices x ; 2 2 V 00 1 V 00 2 and x ; 3 2 V 00 1 V 00 3 Supposethat x ; 2 and x ; 3 haveacommonneighbor y in X 00 1 .Since G isclaw-free, x ; 2 x ; 3 2 E G and V 2 V 0 2 x ; 2 x ; 3 V 0 3 V 3 v 3 P ; 4 v 4 V 4 V 0 4 isaninducedpathonatleast 10vertices.Thuswemayassumethat x ; 2 hasaneighbor y in V 00 1 thatisnotadjacent to x ; 3 andthat x ; 2 x ; 3 = 2 E G .Itfollowsthat V 2 V 0 2 x ; 2 yV 1 v 1 P ; 3 v 3 V 3 V 0 3 x ; 3 is aninducedpathonatleast10vertices.Similarly,if V 00 3 isnonemptyand V 00 3 V 00 i = ; for i 2f 1 ; 2 ; 4 g then V 1 V 0 1 x ; 2 V 0 2 V 2 v 2 P ; 3 v 3 V 3 V 0 3 V 00 3 isaninducedpathcontainingat least10vertices. Bysymmetry,weconcludethat V 00 i V 00 j = ; when1 i
PAGE 49

If v 0 isadjacentto v i for i 2f 3 ; 4 ; 7 ; 8 g ,then G containsa9-cycle.Weconsiderthe casewhen v 0 isadjacentto v 5 and,as G isclaw-free, v 6 .Because G is4-connected, v 3 hasaneighbor v 00 thatdoesnotliein C ;as G isclaw-free, v 00 isalsoadjacentto v 2 or v 4 .Itfollowsthat f v 10 ;v 1 ;:::;v 6 ;v 0 ;v 00 g isthevertexsetofa9-cycle.Thus,wemay assumethat v 0 isadjacentto v 2 or v 9 ;if v 0 isadjacenttoboth,then v 9 v 0 v 2 v 3 :::v 9 isa9-cycle.Weconcludethateveryvertexwithaneighboron C hasexactlythree neighborson C whichareconsecutive. For1 i 10,let V i = N v i )]TJ/F18 7.9701 Tf 6.586 0 Td [(1 N v i N v i +1 whereindicesaretaken modulo10.Ifthereisavertex w= 2 V C [ S i 2 [10] V i thathasaneighbor w i insome V i ,then h w i ; v i )]TJ/F18 7.9701 Tf 6.586 0 Td [(1 ;v i +1 ;w i isaclaw.Thuswemayassumethatthesets V 1 ;:::;V 10 partition V G )]TJ/F20 11.9552 Tf 9.728 0 Td [(V C .Ifthereisanedgejoining V i and V j when j i )]TJ/F20 11.9552 Tf 9.727 0 Td [(j j 2mod10, then G containsa9-cycle.Iftherearetwononconsecutivevalues i
PAGE 50

5.Pancyclicityof f K 1 ; 3 ;N ; 2 ; 2 g f K 1 ; 3 ;N ; 2 ; 2 g f K 1 ; 3 ;N ; 2 ; 2 g -freegraphs Throughoutthischapter,weusethefollowingtosimplifythenotation.Let G be agraphandlet K G bethecompletegraphwithvertexset V G .Forasubgraph H of G andaset S E K G ,wewrite H S ifeither H isaninducedsubgraphof G or S E G 6 = ; .Forexample,if G isaclaw-freegraphwitha4-cycle abcda such thatthereisanothervertex v andanedge va ,wesaythat h a ; v;b;d i!f vb;vd;bd g seeFigure5.1Ifwefurtherknowthat G hasno5-cycle,wesay h a ; v;b;d i!f bd g asitisimmediatelyclearthat G containsa5-cycleifeither vb or vd isanedge. a b c d v Figure5.1:If G isclaw-free,then h a ; v;b;d i!f vb;vd;bd g Tosimplifynotation,weuse N abc ; a 1 a 2 :::a i ;b 1 b 2 :::b j ;c 1 c 2 :::c k todenote acopyof N i;j;k withvertexset f a;b;c g[f a 1 ;a 2 ;:::;a i g[f b 1 ;b 2 ;:::;b j g[ f c 1 ;c 2 ;:::;c k g andedgeset f aa 1 ;a 1 a 2 ;:::a i )]TJ/F18 7.9701 Tf 6.586 0 Td [(1 a i g[f bb 1 ;b 1 b 2 ;:::b j )]TJ/F18 7.9701 Tf 6.587 0 Td [(1 b j g[ f cc 1 ;c 1 c 2 ;:::c k )]TJ/F18 7.9701 Tf 6.586 0 Td [(1 c k g .If k =0,wewrite N abc;a 1 a 2 :::a i ;b 1 b 2 :::b j 5.1ShortCycles Inthissectionweprovethata4-connected, f K 1 ; 3 ;N ; 2 ; 2 g -freegraphcontains cyclesoflength3,4and5.Wewilldothisbyshowingthefollowingstrongerresult. Lemma5.1. If G isa4-connected f K 1 ; 3 ;N g -freegraph,where N 2 f N ; 2 ; 2 ;N ; 2 ; 1 ;N ; 1 ; 1 g ,then G containscyclesoflength3,4and5. Proof: Let G bea4-connected, f K 1 ; 3 ;N g -freegraph.Notethatas G isclawfreeandhasminimumdegreeatleastfour, G necessarilycontainsatriangle.To demonstratetheexistenceof4-and5-cycles,weproceedbyconsideringthedistinct choicesfor N separately. 40

PAGE 51

Case1: N = N ; 1 ; 1. ByTheorem3.7,if G is f K 1 ; 3 ;N ; 1 ; 0 g -freethen G ispancyclic.Therefore G mustcontainaninducedcopyof N ; 1 ; 0,whichwedenoteby N 1 = N a 0 b 0 c 0 ; a 1 a 2 a 3 a 4 a 5 ;b 1 .Since G hasminimumdegreeatleast4and N 1 isinduced, c 0 isadjacenttoapairofvertices u 1 and u 2 thatlieoutsideof N 1 .Let N u i bethe copyof N ; 1 ; 1givenby N a 0 b 0 c 0 ; a 1 a 2 a 3 a 4 ;b 1 ;u i for i 2f 1 ; 2 g Supposerstthat G doesnotcontaina4-cycle,sothatbyClaim4.5, u 1 and u 2 areadjacent.Now,as G containsno C 4 u 1 and u 2 havenocommonneighboraside from c 0 ,andfurtherif u 1 and u 2 areadjacenttodistinctvertices x and y ,respectively, then xy= 2 E G .For i 2f 1 ; 2 g N u i !f a 2 u i ;a 3 u i ;a 4 u i g sinceallotherpossibleedges immediatelyresultina C 4 .If a 2 u i isanedge,then h a 2 ; a 1 ;a 3 ;u i i!f a 3 u i g .Thus u 1 and u 2 musthaveeitheracommonneighbororadjacentneighborsamongst a 2 a 3 and a 4 ,implying C 4 G ,acontradiction. Supposethenthat G doesnotcontain C 5 .Thisimpliesthat u i isnotadjacent to a 1 ;a 2 or b 1 ,andthatif u i isadjacentto b 0 ,then u 3 )]TJ/F21 7.9701 Tf 6.587 0 Td [(i isnotadjacentto a 0 for i 2f 1 ; 2 g .Assumerstthatneither u 1 nor u 2 isadjacenttoeitherof a 0 or b 0 .As G is N ; 1 ; 1-free N u i isnotinduced,so u i musthavesomeneighbor a p 2f a 3 ;a 4 g Theclaw h a p ; u i ;a p )]TJ/F18 7.9701 Tf 6.587 0 Td [(1 ;a p +1 i thenimpliesthateach u i isadjacenttoapairofadjacent verticesin f a 3 ;a 4 ;a 5 g .Thisimpliesthat C 5 V G Thus,wemayassumethat u 1 isadjacenttooneof a 0 or b 0 .As N isnotinduced and G containsno C 5 ,theappropriatechoiceof h a 0 ; u 1 ;a 1 ;b 0 i or h b 0 ; u 1 ;b 1 ;a 0 i implies that a 0 and b 0 arebothadjacentto u 1 .Aseither u 2 b 0 or u 2 a 0 wouldcreatea C 5 N u 2 !f u 2 a 3 ;u 2 a 4 g .Supposerstthat u 2 a 3 2 E G .As u 2 isnotadjacentto a 2 ,the claw h a 3 ; u 2 ;a 2 ;a 3 i impliesthat u 2 a 4 2 E G ,sowemayassume u 2 a 4 2 E G .This thenimpliesthat u 1 hasnoneighborin f a 3 ;a 4 ;a 5 g ,asanyofthesepossibleedges wouldcompletea C 5 in G .If u 1 u 2 wasanedgeof G ,then u 1 u 2 c 0 a 0 b 0 u 1 isa5-cycle, soweconcludethat u 1 musthavesomeneighbor v thatliesoutsideof V N 1 [f u 2 g 41

PAGE 52

However,then N a 0 b 0 u 1 ; a 1 a 2 a 3 a 4 ;b 1 ;v immediatelyforcesa5-cyclein G unless v is adjacentto a 3 .However,then v isadjacenttoeither a 2 or a 4 ,whichimpliesthat G contains C 5 Case2: N = N ; 2 ; 1. ByCase1,if G is f K 1 ; 3 ;N ; 1 ; 1 g -freethen G containscyclesoflength4and5 solet N 1 = N a 0 b 0 c 0 ; a 1 a 2 a 3 a 4 ;b 1 ;c 1 beaninducedcopyof N ; 1 ; 1in G Supposethat C 4 isnotasubgraphof G .Since G hasminimumdegreeatleast 4, b 1 isadjacenttothreevertices u 1 ;u 2 ;u 3 notin V N 1 .ByClaim4.5,wemay assumethat u 3 b 0 ;u 1 u 2 2 E G since N b 1 induces2 K 2 .Additionally, c 0 hasa neighbor v 1 notin V N 1 ;notethat v 1 6 = u i ,as C 4 6 G .For i 2f 1 ; 2 g ,let N u i = N a 0 b 0 c 0 ; a 1 a 2 a 3 ;b 1 u i ;c 1 ,andnotethat N u i !f u i a 1 ;u i a 2 ;u i a 3 ;u i c 1 g .Ifboth u 1 and u 2 areadjacenttoverticesin f a 1 ;a 2 ;a 3 g ,theneither G containsa4-cycleor,without lossofgenerality, u 1 a 3 and u 2 a 1 areedgesand a 2 isadjacenttoneither u 1 nor u 2 .This impliesthat h a 1 ; a 0 ;a 2 ;u 2 i isaninducedclaw.So,wemayassume u 2 c 1 2 E G and u 1 c 1 = 2 E G ,else G containsa4-cycle. As G 4, c 1 isadjacenttosome v 2 notin V N 1 where v 2 6 = v 1 and v 2 6 = u i ,else G containsa4-cycle.ByClaim4.5, v 2 u 2 2 E G .Now, N a 0 b 0 c 0 ; a 1 a 2 a 3 ;b 1 u 1 ;c 1 !f u 1 a 1 ;u 1 a 2 ;u 1 a 3 g and N a 0 c 0 b 0 ; a 1 a 2 a 3 ;c 1 v 2 ;b 1 f v 2 a 1 ;v 2 a 2 ;v 2 a 3 g .If u 1 and v 2 haveacommonneighbor,then G hasa4cycle.Hencewemayassumethateither f v 2 a 1 ;v 2 a 2 ;u 1 a 3 ;u 1 a 4 g E G or f u 1 a 1 ;u 1 a 2 ;v 2 a 3 ;v 2 a 4 g E G ,butnotboth.Theneither N a 1 a 2 v 2 ; a 0 b 0 b 1 ;a 3 a 4 ;c 1 or N a 1 a 2 u 1 ; a 0 c 0 c 1 ;a 3 a 4 ;b 1 isnecessarilyinduced. Nextassumethat G containsnocopyof C 5 .ByCase1, G containsaninduced N ; 1 ; 1, N 2 = N a 0 b 0 c 0 ; a 1 a 2 a 3 a 4 ;b 1 ;c 1 .Since G 4, c 1 hasdistinctneighbors u 1 ;u 2 and u 3 outsideof V N 2 where,withoutlossofgenerality, u 1 and u 2 are adjacent.Henceneither u 1 nor u 2 areadjacenttoanyvertexin f a 0 ;a 1 ;b 0 ;b 1 g 42

PAGE 53

Now h c 1 ; c 0 ;u 3 ;u 2 i!f u 3 c 0 ;u 2 c 0 ;u 2 u 3 g ,soassumerstthat u 3 c 0 2 E G .Then for i 2f 1 ; 2 g thenets N a 0 c 0 b 0 ; a 1 a 2 a 3 ;c 1 u i ;b 1 !f u i a 2 ;u i a 3 g .This,alongwiththe factthat G isclaw-free,impliesthat u 1 and u 2 haveadjacentneighborsin f a 2 ;a 3 ;a 4 g so C 5 G .Consequently, u 3 c 0 = 2 E G ,soassumeinsteadthat u 2 u 3 2 E G ,which impliesthatnoneof u 1 ;u 2 and u 3 isadjacenttoanyof f c 0 ;a 0 ;b 0 ;a 1 ;b 1 g .Hence,as G containsno C 5 ,foreach i 2f 1 ; 2 ; 3 g itfollowsthat N a 0 c 0 b 0 ; a 1 a 2 a 3 ;c 1 u i ;b 1 f u i a 2 ;u i a 3 g sothattwoofthevertices f u 1 ;u 2 ;u 3 g haveacommonneighborin f a 2 ;a 3 g Thisforcesacopyof C 5 in G ,sowemayassumethat u 2 c 0 isanedgein G ,butneither c 0 u 3 nor u 2 u 3 are.Then N a 0 c 0 b 0 ; a 1 a 2 a 3 ;c 1 u 3 ;b 1 !f u 3 a 2 ;u 3 a 3 g .Notethatas u 3 isadjacentto c 1 and N 2 isinduced,if u 4 hasnonadjacentneighborsin f a 0 ;:::;a 4 g then G hasaninducedclaw.Hence,if u 3 a 4 2 E G ,then N c 0 a 0 b 0 ; c 1 u 3 a 4 ;a 1 a 2 ;b 1 isinduced,sowemustinfacthavethat u 3 a 2 and u 3 a 3 arein E G .Itthenfollows that N a 2 u 3 a 3 ; a 1 a 0 b 0 ;c 1 u 2 ;a 4 isinduced,thenalcontradictionneededtocomplete thiscase. Case3: N = N ; 2 ; 2. ByCase2,wemayassumethat G isnot N ; 2 ; 1-free,solet N 3 = N a 0 b 0 c 0 ; a 1 a 2 a 3 ;b 1 b 2 ;c 1 beaninducedsubgraphof G .Since G hasminimumdegree atleast4and N 3 isinduced, c 1 hasatleastthreeneighborsoutsideof V N 3 ,call them u 1 ;u 2 and u 3 .As G isclaw-free,wemayassumethat u 1 u 2 2 E G Assumerstthat G containsno4-cycle,sothat u 3 c 0 isanedgein G byClaim4.5. Now,for i 2f 1 ; 2 g N a 0 b 0 c 0 ; a 1 a 2 ;b 1 b 2 ;c 1 u i !f u i a 1 ;u i a 2 ;u i b 1 ;u i b 2 g .Since u 1 and u 2 havenocommonneighborsoutsideof c 1 ,wemayconcludewithoutlossofgenerality that u 1 a 2 and u 2 b 2 areedgesin G as G isclaw-free.seeFigure5.2Wealsohave thatexactlyoneof u 1 a 1 or u 1 a 3 isalsoin G ,aspossiblyis u 2 b 1 Now, u 3 hastwoneighborsasidefrom c 0 and c 1 ,callthem v 1 and v 2 .Firstassume v 1 = a 3 ,so v 2 a 3 isanedgebyClaim4.5.If u 1 a 3 isanedge,then u 1 a 3 u 3 c 1 u 1 isa 4-cycle,so u 1 a 1 isanedgeinstead.Thenet N a 1 a 2 u 1 ; a 0 b 0 ;a 3 u 3 ;u 2 b 2 istheninduced 43

PAGE 54

a4-cycleset-up b5-cycleset-up a 0 a 1 a 2 a 3 b 0 b 1 b 2 c 0 c 1 u 1 u 2 u 3 a 0 a 1 a 2 a 3 b 0 b 1 b 2 c 0 c 1 u 1 u 2 u 3 Figure5.2:Showing G contains4-and5-cycleswhen N = N ; 2 ; 2. or G containsa4-cycle. Thus,assume v 1 6 = a 3 and v 2 6 = a 3 .ByClaim4.5, v 1 and v 2 arenecessarilyadjacent.Withoutlossofgenerality,thefactthat G isclaw-freeandthenets N a 0 b 0 c 0 ; a 1 a 2 ;b 1 b 2 ;u 3 v i for i 2f 1 ; 2 g implythat v 1 a 2 and v 2 b 2 areedgesin G and possibly v 1 a 1 and v 2 b 1 .If v 2 b 1 = 2 E G ,then N u 3 v 1 v 2 ; c 0 a 0 ;a 2 u 1 ;b 2 b 1 isinduced. Otherwise, N a 0 b 0 c 0 ; a 1 a 2 ;b 1 v 2 ;c 1 u 2 isinduced,so G containsa4-cycle. Finally,supposethat G containsno5-cycle;weproceedbyconsideringhowmany of u 1 ;u 2 ; and u 3 areadjacentto c 0 andnotethatifallthreeoftheseverticesare adjacentto c 0 ,weimmediatelyhavea C 5 seePartbofFigure5.2.Thus,assume that N c 0 f u 1 ;u 2 ;u 3 = ; ,whichimpliesthat u 1 ;u 2 and u 3 arepairwiseadjacent, since G isclaw-free.Thenets N u i = N a 0 b 0 c 0 ; a 1 a 2 ;b 1 b 2 ;c 1 u i implythateach u i is adjacenttooneof a 2 or b 2 ,resultingina C 5 in G Nextassumethattwoof u 1 ;u 2 ; and u 3 areadjacentto c 0 .Since u 1 u 2 2 E G wemusthavethat u 1 and u 2 areadjacentto c 0 ,while u 3 isnot. As G 4and G containsno C 5 ,thereexistdistinctvertices v 1 and v 2 outsideof f u 1 ;u 2 ;u 3 ;a 0 ;a 1 ;a 2 ;b 0 ;b 1 ;b 2 ;c 0 ;c 1 g suchthat u 1 v 1 and u 2 v 2 arein G .If v 1 = a 3 ,then v 2 6 = a 3 and,since N a 0 b 0 c 0 ; a 1 a 2 ;b 1 b 2 ;c 1 u 3 isnotinduced, u 3 b 2 2 E G .However, 44

PAGE 55

since G doesnotcontaina C 5 ,thisimpliesthat N a 0 b 0 c 0 ; a 1 a 2 ;b 1 b 2 ;u 2 v 2 isaninduced copyof N ; 2 ; 2.Thus v 1 6 = a 3 andsimilarly v 2 6 = a 3 .Then,inamannersimilarto thepreviouscases,thenets N a 0 b 0 c 0 ; a 1 a 2 ;b 1 b 2 ;c 1 u 3 and N a 0 b 0 c 0 ; a 1 a 2 ;b 1 b 2 ;u i v i for i 2f 1 ; 2 g implythat C 5 G Thuswemayassumethatexactlyoneof u 1 ;u 2 and u 3 isadjacentto c 0 ,in particularweclaimthat u 3 c 0 mustbein G .Ifinstead u 1 istheonlyvertexin f u 1 ;u 2 ;u 3 g adjacentto c 0 ,then h c 1 ; u 2 ;u 3 ;c 0 i impliesthat c 0 c 1 u 3 u 2 u 1 c 0 isa5-cycle in G .Thuswehavethat u 3 c 0 isanedgein G ,andfurther N u 1 and N u 2 implythatat mostoneof u 1 a 2 or u 2 a 2 isanedgesince u i a 2 forcestheedge u i a 3 whichwouldthen completea5-cyclein G .Asneither N u 1 nor N u 2 isinduced,weassumerstthat u 1 a 2 oridentically u 2 a 2 isanedgeof G ,sothat u 1 a 3 and u 2 b 2 areedgesof G aswell. Now, u 3 hastwoneighbors v 1 and v 2 distinctfrom N 3 [f u 1 ;u 2 g .Neither v 1 nor v 2 isadjacenttoanyof V N 1 [f u 1 ;u 2 g)-262(f c 0 ;c 1 g since G doesnothavea5cycle.Ifboth v 1 and v 2 areadjacentto c 0 ,then h u 3 ; v 1 ;v 2 ;c 1 i!f v 1 v 2 ;v 1 c 1 ;v 2 c 1 g whichimpliesthat C 5 G .Thuswemayassumethat v 2 c 0 isnotanedge,butthen N a 0 b 0 c 0 ; a 1 a 2 ;b 1 b 2 ;u 3 v 2 isaninducedcopyof N ; 2 ; 2. Thusneither u 1 a 2 nor u 2 a 2 isanedgeandwemayassumethatboth u 1 b 2 and u 2 b 2 areedges.Notethat u 3 isnotadjacenttoanyof f u 1 ;u 2 ;b 0 ;b 1 ;b 2 ;a 0 ;a 1 g ,sincethere isno5-cycle.Then N a 0 b 0 c 0 ; a 1 a 2 ;b 1 b 2 ;c 1 u 3 !f u 3 c 0 ;u 3 a 2 g ,butwecannothave both u 3 c 0 and u 3 a 2 in G .If u 3 a 2 2 E G ,then h c 1 ; c 0 ;u 3 ;u 1 i!f c 0 u 3 ;c 0 u 1 ;u 1 u 3 g in eachcasethereisa5-cycle. Thuswemayassumethat u 3 c 0 isanedge.Thevertex u 3 has2neighbors v 1 and v 2 otherthan N 1 [f u 1 ;u 2 g)-279(f a 3 g .If v 2 = a 3 ,then h u 3 ; c 0 ;v 1 ;v 2 i!f v 1 v 2 g butthen h a 0 b 0 c 0 ; a 1 a 2 ;b 1 b 2 ;u 3 v 1 i isaninducedcopyof N ; 2 ; 2,thus v 2 6 = a 3 Now, N a 0 b 0 c 0 ; a 1 a 2 ;b 1 b 2 ;u 3 v i !f v i c 0 ;v i a 2 g .Ifboth v 1 c 0 and v 2 c 0 areedges, then h u 3 ; v 1 ;v 2 ;c 1 i!f v 1 v 2 ;v 1 c 1 ;v 2 c 1 g ,andinanycase G hasa5-cycle.Soassumethat v 2 c 0 isnotanedge,implyingthat v 2 a 2 ,andthus v 2 a 3 ,areedges.Then 45

PAGE 56

h c 0 ; c 1 ;b 0 ;v 1 i!f v 1 c 1 g .Now v 1 hasaneighbor x notin N 1 so h a 0 b 0 c 0 ;a 1 a 2 ;b 1 b 2 ;v 1 x i isinduced.Thiscontradictionimpliesthat G isnotclaw-free. 5.2TechnicalLemmas Inthissection,wegiveanumberoftechnicallemmasthatwillgreatlysimplifythe casestructureoftheproofinSection5.3,whereinwedemonstratethata4-connected f K 1 ; 3 ;N ; 2 ; 2 g -freegraphoforder n containscycleoflength ` for6 ` n Let G bea4-connectedclaw-freegraph,let C beacyclein G oflength s ,where 5 s< j V G j ,andassumethat G containsno s +1-cycle.Since G is4-connected, foreachvertex v 2 V G )]TJ/F20 11.9552 Tf 10.854 0 Td [(V C thereexistfourinternallydisjoint v )]TJ/F20 11.9552 Tf 10.853 0 Td [(C paths,each containingauniquevertexfrom C .Let w;x;y;z 2 V C bethesevertices,andlet P x denotethepathcontaining x P y denotethepathcontaining y ,andsoon.Assume thatamongstallchoicesof v;w;x;y and z j P x j + j P y j + j P z j isminimum. Theclawcenteredat v withonevertexfrom P x ;P y and P z isnotinduced,thus v liesonatriangle T .For a 2f w;x;y;z g let F a denotetheunique a )]TJ/F20 11.9552 Tf 11.379 0 Td [(T paththat isasubpathof P a ,andlet a 0 betheendpointof F a in T .Itispossiblethat a 0 = a if v isadjacentto a ,andalsothereforepossiblethat F a isatrivialpathapathof orderone.However,since v 2 V G )]TJ/F20 11.9552 Tf 12.135 0 Td [(V C and v 2f x 0 ;y 0 ;z 0 g ,atmosttwoof x 0 y 0 or z 0 lieon C .Finally,let F = T [ S a 2f x;y;z g F a andnotethattheminimality of j P x j + j P y j + j P z j impliesthat F )-222(f x;y;z g isinduced. Let xx 1 :::x p +1 = x 0 yy 1 :::y q +1 = y 0 ,and zz 1 :::z t +1 = z 0 denotethevertices on F x F y and F z ,respectively.Also,let I x = x 1 :::x p I y = y 1 :::y q and I z = z 1 :::z t denotetheinteriorsubpathsof F x F y and F z ,andnotethat I x I y or I z maybe empty.Theassumptionthat G containsno s +1-cyclealsoyieldsthat x )]TJ/F20 11.9552 Tf 7.085 -4.338 Td [(x + y )]TJ/F20 11.9552 Tf 7.085 -4.338 Td [(y + and z )]TJ/F20 11.9552 Tf 7.085 -4.338 Td [(z + areedgesin G astheclaws h x ; x 1 ;x )]TJ/F20 11.9552 Tf 7.084 -4.338 Td [(;x + i h y ; y 1 ;y )]TJ/F20 11.9552 Tf 7.084 -4.338 Td [(;y + i ,and h z ; z 1 ;z )]TJ/F20 11.9552 Tf 7.085 -4.338 Td [(;z + i arenotinduced. 46

PAGE 57

Uptorelabelingandreversingtheorientationof C ,assume j I x jj I y jj I z j and alsothat x y and z appearon C inthisorderwhentraversing C intheclockwise direction.Asaresult,if v isadjacenttoexactlyonevertexon C thenitis z 0 = z andif v isadjacenttoexactlytwoverticeson C theyare y 0 = y and z 0 = z .see Figures5.3,5.4,and5.5 x x 1 x p x 0 y y 1 y q y 0 z z 1 z t z 0 Figure5.3:Thefan F whennoneof x 0 y 0 ,or z 0 ison C x x 1 x p x 0 y y 1 y q y 0 z = z 0 Figure5.4:Thefan F when z 0 ison C ,butneither x 0 nor y 0 ison C Fortheremainderofthissection,whenconvenientwewilllet a denoteanarbitraryelementof f w;x;y;z g andwewilluse a inaexiblemannerthatallowsusto 47

PAGE 58

x x 1 x p x 0 y = y 0 z = z 0 Figure5.5:Thefan F whenboth y 0 and z 0 areon C ,but x 0 isnot on C introducenotationrelatingtoalloftheverticesin f w;x;y;z g withouttheneedfor tediousrepetition.Forinstance,giventhenotationdenedabove,whenunambiguouswewillreferto P a ;F a I a andsoon.Wealsowillfrequentlyomittheassumption that a issomevertexin f w;x;y;z g ,againinordertominimizerepetition.Finally, tosimplifynotation, F a = aa 0 so a 6 = a 0 ,but a 1 doesnotexist,thenwewillreferto a 0 as a 1 Ourrstlemmafollowsroutinelyfromtheminimalityof F andtheassumption that G containsno s +1-cycle. Lemma5.2. If f x 0 ;y 0 ;z 0 g V C = ; thentherearenoedgesbetween V F )-37(f x;y;z g and V C exceptfor xx 1 yy 1 ,and zz 1 .If f x 0 ;y 0 ;z 0 g V C = f z g ,i.e. z = z 0 ,then therearenoedgesbetween V F )-326(f x;y;z g and V C except xx 1 yy 1 x 0 z ,and y 0 z .If f x 0 ;y 0 ;z 0 g V C = f y;z g and j I x j 1 ,thentherearenoedgesbetween V F )-285(f x;y;z g and V C except x 0 y x 0 z x 1 x ,andpossibly x 1 u foratmostone u 2 V C )-222(f x g 48

PAGE 59

Proof: Ineachcase,itisclearifthereisanyvertex v 2 V C suchthat v has aneighborin V F )-222(f x;x 1 ;y;y 1 ;z;z 1 g ,then F isnotminimal. Firstsuppose f x 0 ;y 0 ;z 0 g V C = ; .seeFigure5.3Ifsomevertex v 2 V C )]TJ -422.701 -23.981 Td [(f x;y;z g hasaneighbor a 1 2f x 1 ;y 1 ;z 1 g ,thenthefanformedbytakingshortestpaths from a 1 to C contradictstheminimalityof F .Asimilarcontradictionarisesifanyof xy 1 xz 1 yx 1 yz 1 zx 1 ,or zy 1 isanedge. Nowassume f x 0 ;y 0 ;z 0 g V C = f z g .seeFigure5.4Ifsomevertex v 2 V C )-245(f x;y g hasaneighbor a 1 2f x 1 ;y 1 g ,thenthefanformedbytakingshortest pathsfrom a 1 to C contradictstheminimalityof F .Asimilarcontradictionarisesif xy 1 or yx 1 isanedge. Finallyweconsider f x 0 ;y 0 ;z 0 g V C = f y;z g and j I x j 1.seeFigure5.5If twoverticesin V C )-124(f x g bothhave x 1 asaneighbor,thenthefanformedbytaking shortestpathsfrom x 1 to C contradictstheminimalityof F Ournextlemmasprovideusefulstructuralinformationaboutvariousintervalsof verticeson C Lemma5.3. If u and v areverticeson C suchthat [ u;v ] C N [ a ] ,then [ u;v ] C inducesacliquein G Proof: Recallthat a )]TJ/F20 11.9552 Tf 7.085 -4.339 Td [(a + 2 E G .Supposethat b and c arenonadjacentvertices in[ u;v ] C suchthat b and c appearinthatorderon C inthepositivedirection.The claw h a ; a 1 ;b;c i!f ba 1 ;ca 1 g .Withoutlossofgenerality,assume ba 1 2 E G ,sothat b= 2f a )]TJ/F20 11.9552 Tf 7.084 -4.338 Td [(;a + g ,lest G containan s +1-cycle.Since c appearsafter b in[ u;v ] C ,we musthave b + 2 [ u;v ] C and b + a 2 E G .Then a )]TJ/F20 11.9552 Tf 7.084 -4.338 Td [(C )]TJ/F20 11.9552 Tf 7.084 -4.338 Td [(b + aa 1 bC )]TJ/F20 11.9552 Tf 7.085 -4.338 Td [(a + a )]TJ/F15 11.9552 Tf 10.132 -4.338 Td [(isan s +1-cycle in G For a 2f w;x;y;z g ,let Q C a =[ a ` ;a r ] C bethelargestintervalof C suchthat a 2 [ a ` ;a r ] C and[ a ` ;a r ] C N [ a ].Whenthecontextisclear,wewillsimplywrite Q a .ByLemma5.3, Q a inducesacliquein G .Notethat Q a contains,ata 49

PAGE 60

minimum,thevertices a;a )]TJ/F15 11.9552 Tf 11.517 -4.338 Td [(and a + .Also,if G [ V C ]= K s wehave Q a = V C forallchoicesof a If G [ V C ] 6 = K s ,thenthemaximalityof Q a impliesthat a isadjacentto neither a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` nor a + r .Additionally,as Q a isaclique,nopairofverticesin Q a can haveacommonneighborin V G )]TJ/F20 11.9552 Tf 11.955 0 Td [(V C ,lest G containacycleoflength s +1. Ournextlemmafollowseasilyfromthemaximalityof[ a ` ;a r ] C andthefactthat G containsno s +1-cycle. Lemma5.4. If V C doesnotinduceacompletegraph,then a ` and a r areonly adjacenttoverticesin V C .Inparticular,neither a ` nor a r isin f w;x;y;z g Proof: Suppose a ` isadjacenttosomevertex v 0 noton C ,andconsiderthe claw h a ` ; a;a )]TJ/F21 7.9701 Tf 0 -8.277 Td [(` ;v 0 i .Asmentionedabove, a ` and a canhavenocommonneighbors outsideof C ,soeither a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` a 2 E G ,whichcontradictsthemaximalityof Q a ,or a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` v 0 2 E G ,formingan s +1-cycle.Thecasewhere a r hassomeneighboroof C isidentical. Inordertosimplifythecycleswedescribethroughouttheremainderofthis chapter,wemakethefollowingobservation. Observation5.5. If Q a 6 = Q b ,thenwecanassume a ` ;a and b ` ;b appearconsecutivelyin C .If Q a = Q b ,thenwecanassume a ` ;a and b appearconsecutivelyin C Let O denotethesetofverticesin V C thathaveaneighboroof C .By Lemma5.4,weknowthatno x 2O canbe a r or a ` foranychoiceof a ,andfurther that x )]TJ/F20 11.9552 Tf 7.084 -4.338 Td [(x + isanedgein G foranysuch x .Hence,wecanreplace x )]TJ/F20 11.9552 Tf 7.085 -4.338 Td [(xx + on C with x )]TJ/F20 11.9552 Tf 7.085 -4.338 Td [(x + toobtainacycleinwhichwemaycontinuetoutilizethestructureensured by Q a asneeded.Further,supposethat x 1 ;:::;x m m 2areverticesin O that appearconsecutivelyon C inthatorder.Lemmas5.3and5.4implythat x )]TJ/F18 7.9701 Tf 0 -7.879 Td [(1 x + m is 50

PAGE 61

anedgein G .Hence,foranyset X ofverticesin O wemaydeneacycle C X in whichthefollowinghold: 1. j V C X j = j V C )]TJ/F20 11.9552 Tf 11.955 0 Td [(X j = s )-222(j X j 2.theverticesin V C X = V C )]TJ/F20 11.9552 Tf 12.307 0 Td [(X appearinexactlythesameorderon C and C X ,and 3.foreach a 2f w;x;y;z g)]TJ/F20 11.9552 Tf 22.015 0 Td [(X Q a )]TJ/F20 11.9552 Tf 12.668 0 Td [(X isacliqueconsistingofconsecutive verticeson C X withendpoints a ` and a r If X = f x 1 ;:::;x m g ,wewillsometimeswrite C x 1 ;:::;x m inplaceofthemore cumbersome C f x 1 ;:::;x m g Lemma5.6. Let a and b bedistinctelementsin f w;x;y;z g ,andlet P bean a )]TJ/F20 11.9552 Tf 12.173 0 Td [(b pathoflength withnointernalverticeson C 1.If 2 4 ,then j a r ;b ` C j )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 and j b r ;a ` C j )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 2.If =5 and ab= 2 E G ,then j a r ;b ` C j 4 and j b r ;a ` C j 4 Proof: Throughouttheproof,let f c;d g = f w;x;y;z g)-352(f a;b g .First,if G [ V C ]= K s ,then s 5clearlyimpliesthat G hasan s +1-cyclewhenthelength of P isbetween2and5.Thus,goingforwardwewillassumethat G [ V C ] 6 = K s Toestablish 1 ,weconsideronlythescenariowhere =4and j a r ;b ` C j 2, asthecases =3and =2andthesymmetriccasewhere =4and j b r ;a ` C j 2 arehandledsimilarly. First,if1 j a r ;b ` C j 2,thenthefactthat Q a and Q b arecompleteallow ustoreplaceeither a r ;b ` or[ a r ;b ` withtheinteriorverticesof P toobtainan s +1cycle.Intheformercase a )]TJ/F20 11.9552 Tf 7.085 -4.338 Td [(a r C )]TJ/F20 11.9552 Tf 7.085 -4.338 Td [(aPbC )]TJ/F20 11.9552 Tf 7.084 -4.338 Td [(b ` b + Ca )]TJ/F15 11.9552 Tf 11.495 -4.338 Td [(isan s +1-cycle,andthelatter case a )]TJ/F20 11.9552 Tf 7.084 -4.338 Td [(a )]TJ/F21 7.9701 Tf 0 -7.294 Td [(r C )]TJ/F20 11.9552 Tf 7.084 -4.338 Td [(aPbC )]TJ/F20 11.9552 Tf 7.085 -4.338 Td [(b ` b + Ca )]TJ/F15 11.9552 Tf 10.978 -4.338 Td [(isan s +1-cycle.Thus,supposenextthat a r = b ` .If j Q a j 4theneither a )]TJ/F23 11.9552 Tf 10.405 -4.338 Td [(6 = a ` or a )]TJ/F21 7.9701 Tf 0 -7.294 Td [(r 6 = a .If a )]TJ/F23 11.9552 Tf 10.406 -4.338 Td [(6 = a ` then a )]TJ/F18 7.9701 Tf 6.587 0 Td [(2 a )]TJ/F21 7.9701 Tf 0 -7.294 Td [(r C )]TJ/F20 11.9552 Tf 7.085 -4.338 Td [(aPbC )]TJ/F20 11.9552 Tf 7.084 -4.338 Td [(b )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` b + Ca )]TJ/F18 7.9701 Tf 6.587 0 Td [(2 51

PAGE 62

isan s +1-cycle,andthecasewhere a )]TJ/F21 7.9701 Tf 0 -7.294 Td [(r 6 = a issimilar.Thereforebysymmetrywe havethat j Q a j = j Q b j =3and a r = b ` .As c hasaneighborin V G )]TJ/F20 11.9552 Tf 12.47 0 Td [(V C Lemma5.4impliesthat c= 2 Q a [ Q b ,sothat aPbCc )]TJ/F20 11.9552 Tf 7.085 -4.338 Td [(c + Ca isan s +1-cyclein G Suppose a 2 Q b .Then,as Q b iscomplete,wecanassume a and b are consecutiveon C .Now,if c and d arenotconsecutiveon C ,then aPbCc )]TJ/F20 11.9552 Tf 7.085 -4.339 Td [(c + Cd )]TJ/F20 11.9552 Tf 7.084 -4.339 Td [(d + Ca isan s +1-cycle.If,instead, c = d )]TJ/F15 11.9552 Tf 11.433 -4.338 Td [(isanedgeon C ,thentheclaw h c ; c )]TJ/F20 11.9552 Tf 7.085 -4.338 Td [(;c 1 ;d + i impliesthat c )]TJ/F20 11.9552 Tf 7.084 -4.338 Td [(d + 2 E G ,so aPbCc )]TJ/F20 11.9552 Tf 7.085 -4.338 Td [(d + Ca isan s +1-cycle.Again,thecasewhere b 2 Q a isidentical. Finallysuppose a r 2 b ` ;b C and a 2 b + r ;b )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` C .Then a )]TJ/F20 11.9552 Tf 7.084 -4.338 Td [(b )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` C )]TJ/F20 11.9552 Tf 7.084 -4.338 Td [(aPbC )]TJ/F20 11.9552 Tf 7.085 -4.338 Td [(b +2 ` b + Ca )]TJ/F15 11.9552 Tf 10.049 -4.338 Td [(is an s +1-cyclethatskipsthevertices b ` and b + ` .Notethat b + ` 6 = b since a r 2 b ` ;b C Therefore,wehavethatthelengthof P is5andthat ab= 2 E G ,so a= 2 Q b and b= 2 Q a .Assumerstthat a r 2 [ b ` ;b C ,andnotethatthismustalsobethecasein C 0 = C c;d .Thus, C 00 = a )]TJ/F20 11.9552 Tf 7.085 -4.339 Td [(a )]TJ/F21 7.9701 Tf 0 -7.294 Td [(r C 0)]TJ/F20 11.9552 Tf 9.382 -4.339 Td [(aPbC 0)]TJ/F20 11.9552 Tf 9.382 -4.339 Td [(a + r b + C 0 a )]TJ/F15 11.9552 Tf 11.165 -4.339 Td [(skips a r and,asitalsoomits c and d ,haslength s +1.Consequently,wemayassumethat a;a r ;b ` and b appearin thatorderalong C inthepositivedirection.If a r and b ` areconsecutiveon C then let C 0 = C c andconsider C 00 = a )]TJ/F20 11.9552 Tf 7.084 -4.338 Td [(a )]TJ/F21 7.9701 Tf 0 -7.294 Td [(r C 0)]TJ/F20 11.9552 Tf 9.381 -4.338 Td [(aPbC 0)]TJ/F20 11.9552 Tf 9.381 -4.338 Td [(b + ` b + C 0 a )]TJ/F15 11.9552 Tf 7.084 -4.338 Td [(.Thiscycleskips a r and b ` on C 0 andhaslength s +1. Itremainstoconsiderwhen j a r ;b ` C j2f 1 ; 2 ; 3 g .If j a r ;b ` C j =1,then a )]TJ/F20 11.9552 Tf 7.085 -4.339 Td [(a )]TJ/F21 7.9701 Tf 0 -7.294 Td [(r C )]TJ/F20 11.9552 Tf 7.085 -4.339 Td [(aPbC )]TJ/F20 11.9552 Tf 7.085 -4.339 Td [(b + ` b + Ca )]TJ/F15 11.9552 Tf 12.774 -4.339 Td [(isan s +1-cyclein G .Similarly,if j a r ;b ` C j =2or j a r ;b ` C j =3,then a )]TJ/F20 11.9552 Tf 7.085 -4.339 Td [(a )]TJ/F21 7.9701 Tf 0 -7.294 Td [(r C )]TJ/F20 11.9552 Tf 7.085 -4.339 Td [(aPbC )]TJ/F20 11.9552 Tf 7.085 -4.339 Td [(b ` b + Ca )]TJ/F15 11.9552 Tf 12.825 -4.339 Td [(and a )]TJ/F20 11.9552 Tf 7.085 -4.339 Td [(a r C )]TJ/F20 11.9552 Tf 7.085 -4.339 Td [(aPbC )]TJ/F20 11.9552 Tf 7.085 -4.339 Td [(b ` b + Ca )]TJ/F15 11.9552 Tf 7.084 -4.339 Td [(,respectively,are s +1-cyclesin G .Thuswemayconcludethat j a r ;b ` C j 4,asdesired, andsymmetrically,that j b r ;a ` C j 4. ThefollowinglemmabyGould,LuczakandPfender[41]willbeusefulaswe proceed. Lemma4.1. Let G beaclaw-freegraphwithminimumdegree G 3 ,andlet C 52

PAGE 63

beacycleoflength t withnohops,forsome t 5 .Set X = f v 2 V C j thereisnochordincidentto v g ; andsupposeforsomechord xy of C wehave j X V xCy j 2 .Then G contains cycles C 0 and C 00 oflengths t )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 and t )]TJ/F15 11.9552 Tf 11.955 0 Td [(2 ,respectively. Lemma5.7. Suppose s = j V C j 6 andlet k =6 if G is N ; 1 ; 1 -free,otherwise let k =5 .Let a and b bedistinctelementsof f w;x;y;z g whereatleastoneof a 0 or b 0 isnoton C and a 1 b isnotanedge.Further,let P = aI a a 0 b 0 I b b havelength .If 2 k andanyofthefollowinghold thereisanedgebetween f a )]TJ/F21 7.9701 Tf 0 -8.277 Td [(` ;a ` ;a g and f b )]TJ/F21 7.9701 Tf 0 -8.277 Td [(` ;b ` ;b g ,or thereisanedgebetween f a;a r ;a + r g and f b;b r ;b + r g ,or Q a = Q b then G containsan s +1 -cycleunlesseither P = avb andtheonlyedgesatisfying oris ab ,or =6 andtheonlyedgesatisfyingorisoneof a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` b )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` or a + r b + r Proof: Noterstthatconditionsandareidenticaluptothereversalof C ,soitsucestoassumethateitherorholds. If Q a 6 = Q b and ab 2 E G ,thensinceweassumethat a 1 b= 2 E G h a ; a 1 ;a ` ;b i!f a ` b g .Further,ifeither a ` b or ab ` isanedgeof G ,then h b ; b 1 ;b ` ;a ` i! f a ` b ` g or h a ; a 1 ;a ` ;b ` i!f a ` b ` g ,respectively.Thereforeanyedgebetween f a;a ` g and f b;b ` g implies a ` b ` isanedge.Uptorenaming,thecasewhen a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` b 2 E G issymmetrictothecasewhen ab )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` 2 E G .Similarly,thecase a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` b ` 2 E G issymmetric tothecase a ` b )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` 2 E G .Thereforewhen Q a 6 = Q b itisenoughtosupposethat oneof a ` b ` a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` b a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` b ` ,or a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` b )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` isanedgeof G 53

PAGE 64

Case1: jOj Firstsuppose Q a = Q b ,sowecanassume a and b appearconsecutivelyon C Select S O)-186(f a;b g ,where j S j = )]TJ/F15 11.9552 Tf 11.525 0 Td [(2.Then C S haslength s )]TJ/F20 11.9552 Tf 11.524 0 Td [( +2and a and b areconsecutiveverticesin C S ,so aPbC S a isan s +1-cyclein G .Thus,for theremainderofthiscasewewillassumethatconditionholdsand Q a 6 = Q b As Q a 6 = Q b ,thenbyObservation5.5,wecanassumeboth aa ` and bb ` areedgesin C .Weshowthatifthereisanedge a b satisfyingconditioni.e. a 2f a;a ` ;a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` g and b 2f b;b ` ;b )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` g ,thenthereisaset S O suchthat C S containsthevertices a and b When a ` b ` 2 E G ,select S O)-292(f a;b g with j S j = )]TJ/F15 11.9552 Tf 12.793 0 Td [(2.ByLemma5.4 a ` ;b ` = 2O ,so a a ` b ,and b ` areallverticesin C S ,andboth aa ` and bb ` lieon C S .Then,thecycle a ` b ` C S )]TJ/F20 11.9552 Tf 7.085 -4.339 Td [(aPbC S a ` haslength s +1. Supposethen,that a )]TJ/F21 7.9701 Tf 0 -8.277 Td [(` b 2 E G .If =2,then a )]TJ/F21 7.9701 Tf 0 -8.277 Td [(` bPaCb )]TJ/F20 11.9552 Tf 7.084 -4.339 Td [(b + Ca )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` isan s +1cycle.When 3select S O)-246(f a;b;a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` g with j S j = )]TJ/F15 11.9552 Tf 12.243 0 Td [(3sothat a b ,and a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` areallverticesin C S andvertices a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` a ` a appearconsecutivelyin C S .Thecycle a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` bPaC S b )]TJ/F20 11.9552 Tf 7.084 -4.338 Td [(b + C S a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` skips a ` andhaslength s +1. Anotherpossibilityisthat a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` b ` 2 E G .If =2,then a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` b ` C )]TJ/F20 11.9552 Tf 7.085 -4.338 Td [(a + a ` aPbCa )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` is an s +1-cycle.When 3select S O)-230(f a;b;a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` g with j S j = )]TJ/F15 11.9552 Tf 12.057 0 Td [(3.Thecycle a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` b ` C S )]TJ/F20 11.9552 Tf 7.085 -4.339 Td [(aPbC S a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` haslength s +1. Finally,weassumethat a )]TJ/F21 7.9701 Tf 0 -8.277 Td [(` b )]TJ/F21 7.9701 Tf 0 -8.277 Td [(` 2 E G .If =2or =3,then a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` b )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` C )]TJ/F20 11.9552 Tf 7.084 -4.339 Td [(a + a ` aPbb ` b + Ca )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` or a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` b )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` C )]TJ/F20 11.9552 Tf 7.085 -4.338 Td [(aPbb ` b + Ca )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` isan s +1-cycle.When 4 select S O)-208(f a;b;a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` ;b )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` g with j S j = )]TJ/F15 11.9552 Tf 11.791 0 Td [(4.Thecycle a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` b )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` C S )]TJ/F20 11.9552 Tf 7.085 -4.338 Td [(aPbC S a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` has length s +1.ThiscompletesCase1. Weknow f w;x;y;z gO ,soitfollowsthatif 4,then G hasan s +1-cycle. Thus,weneedonlytoconsiderthecaseswhere =5and jOj =4sospecically O = f w;x;y;z g ,andwhere =6and4 jOj 5. 54

PAGE 65

Case2: =5and O = f w;x;y;z g Case2.1 Suppose Q a = Q b or a ` b ` 2 E G Let S = f c;d g .If Q a = Q b ,thenwemayassume a and b areconsecutive on C andwelet C 0 = aPbC S a ,andif a ` b ` 2 E G let C 0 = a ` b ` C S )]TJ/F20 11.9552 Tf 7.084 -4.339 Td [(aPbC S a ` Notethatinbothcases C 0 haslength s +2.Ifthecycle C 0 containsahop,then G hasan s +1-cycle,sowesupposethat C 0 doesnotcontainahop. Let u 2 V C )]TJ/F15 11.9552 Tf 12.104 0 Td [( O[f c ` ;c r g andnote d u 4.Supposerstthat u doesnot haveachordin C 0 ,whichimpliesthat u mustbeadjacenttoboth c and d which arenotin V C 0 .As u= 2f c ` ;c r g h c ; c 1 ;u;c ` i!f uc ` g and h c ; c 1 ;u;c r i!f uc r g implyingthat c ` u and c r u areedges.As u doesnothaveachordin C 0 ,then c ` uc r appearconsecutivelyand c ` c r isahopon C 0 .Thiscontradictionimpliesthat G hasan s +1-cycle.Notethatwhen Q a = Q b that ab isachordof C 0 ,and when a ` b ` 2 E G then a ` a and b ` b arechordsof C 0 .Thereforeeveryvertexin V C 0 )-305(f c ` ;c r g musthaveachordin C 0 .Consequently,everychordof C 0 skips nounchordedverticesandthussatisestheconditionsofLemma5.2,so G hasan s +1-cycle. Case2.2 Oneof a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` b a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` b ` or, a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` b )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` isanedge. Suppose a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` = 2O .Then jO)-313(f a;b gj = )]TJ/F15 11.9552 Tf 13.05 0 Td [(3and jO)-313(f a;b;b )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` gj )]TJ/F15 11.9552 Tf 13.05 0 Td [(4. Thisimpliesthatregardlesswhichof a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` b a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` b ` ,or a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` b )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` isanedgeof G ,either S = O)-115(f a;b;a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` g or S = O)-116(f a;b;a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` ;b )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` g canbeusedtoshowthat G hasan s +1 cycleviaanidenticalargumentaswasusedinCase1. Thus a )]TJ/F21 7.9701 Tf 0 -8.277 Td [(` 2O ;withoutlossofgeneralityassume a )]TJ/F21 7.9701 Tf 0 -8.277 Td [(` = c .If a )]TJ/F21 7.9701 Tf 0 -8.277 Td [(` b )]TJ/F21 7.9701 Tf 0 -8.277 Td [(` = cb )]TJ/F21 7.9701 Tf 0 -8.277 Td [(` isan edge,then aPbCc )]TJ/F20 11.9552 Tf 7.085 -4.338 Td [(b )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` C )]TJ/F20 11.9552 Tf 7.085 -4.338 Td [(a isan s +1-cycle.Also,if a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` b ` = cb ` isanedge,then h c ; c 1 ;a ` ;b ` i!f a ` b ` g whichbyCase2.1implies G hasan s +1-cycle.Finally,if a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` b = bc isanedge,thentheclaw h b ; b 1 ;c;b ` i!f b 1 c;b ` c g sowemayassumethat b 1 c isanedge.Thenthepath cI b b 0 a 0 I a a haslength ,where c ` a ` 2 E G since a ` 2 Q c .AgainbyCase2.1weknow G hasan s +1-cycle. 55

PAGE 66

Case3 =6. Noterstthatsinceweareassuming =6wemayalsoassumethat G is N ; 1 ; 1-free,andrecallthatbyCase1wehavethat4 jOj 5.Wewillrstform an s +3-cycle C 00 thathasalltheverticesof P appearingconsecutively.Wewill thenusethis s +3-cycletoforman s +1-cycle.Let R bethesetofverticesin V C V C 00 suchthatforeach x 2 R ,thesubpath x )]TJ/F20 11.9552 Tf 7.084 -4.339 Td [(xx + in C isnotasubpath of C 00 .Thus R isthesetofverticeswherewehaverearranged" C toform C 00 .We depictthevariantsof C 00 andtheirassociatedchoicesof R inFigure5.6. Firstsuppose Q a = Q b ,sowecanassume a and b appearconsecutivelyon C .Ifwelet S = f c;d g ,then C S haslength s )]TJ/F15 11.9552 Tf 11.974 0 Td [(2and a and b arealsoconsecutive on C S .Consequently,choosing C 00 = aPbC S a isan s +3-cycle.Inthiscase R = f a;b g If,instead, Q a 6 = Q b ,thenwecanassumeboth aa ` and bb ` areedgesof C Weshowthatifthereisanedge a b satisfyingconditioni.e. a 2f a;a ` ;a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` g and b 2f b;b ` ;b )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` g ,thenthereisaset S O suchthat C 00 = C S containsthe vertices a and b When a ` b ` 2 E G set S = f c;d g .ByLemma5.4 a ` ;b ` = 2O ,so a a ` b ,and b ` all liein C S ,whichalsostillcontains aa ` and bb ` .Thecycle C 00 = a ` b ` C S )]TJ/F20 11.9552 Tf 7.085 -4.338 Td [(aPbC S a ` thenhaslength s +3and R = f a;b;a ` ;b ` g Suppose a )]TJ/F21 7.9701 Tf 0 -8.277 Td [(` b 2 E G .Select r 2f a )]TJ/F21 7.9701 Tf 0 -8.277 Td [(` g ,sothat a b ,and a )]TJ/F21 7.9701 Tf 0 -8.277 Td [(` areallverticesin C r and a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` ;a ` and a appearconsecutivelyin C r .Itthenfollowsthatchoosing C 00 = a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` bPaC r b )]TJ/F20 11.9552 Tf 7.084 -4.338 Td [(b + C r a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` skips a ` andhaslength s +3and R = a;b;a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` ;b )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` ;b + Similarly,if a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` b ` 2 E G ,thenselect r 0 2f c;d g)-332(f a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` g .Thecycle C 00 = a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` b ` C r 0 )]TJ/F20 11.9552 Tf 7.085 -4.338 Td [(aPbC r 0 a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` thenhaslength s +3and R = a;b;a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` ;b ` Finally,if a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` b )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` 2 E G ,then C 00 = a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` b )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` C )]TJ/F20 11.9552 Tf 7.085 -4.338 Td [(aPbCa )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` isan s +3-cycleand R = a;b;a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` ;b )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` 56

PAGE 67

Q a = Q b a ` b ` a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` b a )]TJ/F21 7.9701 Tf 0 -8.277 Td [(` b ` a )]TJ/F21 7.9701 Tf 0 -8.277 Td [(` b )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` Figure5.6:Formingthecycle C 00 from C S .Thecentralgure isthecasewhen Q a = Q b ,theothersarelabeledaccordingto whichedgewasusedtoform C 00 .Non-shadedverticesarein R Ineachcase C 00 isan s +3-cyclethatcontainstheverticesof P consecutively. If C 00 hasahop,thenlet C 0 bethe s +2-cycleformedfrom C 00 bytakingthehop, otherwiselet C 0 = C 00 .Since P isinduced, C 0 stillhastheinternalverticesof P appearingconsecutively.Notethatwemayassume C 0 hasnohops,asifitdid,then C 0 6 = C 00 and G containsan s +1-cycle.Let X C 0 bethesetofverticesin C 0 that arenottheendpointofachordof C 0 .Thusif C 0 hasachordthatskipsatmost2 verticesin X C 0 ,thenLemma5.2implies G hasan s +1-cycle.Soweassumethat everychordin C 0 skipsatleastthreeverticesin X C 0 .Let S 0 = V C )]TJ/F20 11.9552 Tf 12.355 0 Td [(V C 0 and notethat j S 0 j 3as P hasveinternalverticesand j C 0 jj C 00 j)]TJ/F15 11.9552 Tf 17.933 0 Td [(1. 57

PAGE 68

Wenowwishtoshowthat X C 0 )]TJ/F20 11.9552 Tf 10.029 0 Td [(V P doesnotcontainfourindependentvertices. Wedothisbyshowingthatanysetoffourindependentverticesin X C 0 )]TJ/F20 11.9552 Tf 12.106 0 Td [(V P has atleastsevenedgesto S 0 implyingthatthereisaninducedclawcenteredatavertex in S 0 .Notethatanyvertex x 2 X C 0 )]TJ/F20 11.9552 Tf 12.223 0 Td [(V P O hastwoneighborsin S 0 sinceit hasdegreeatleast4.Weseektolimitthenumberofverticesin X C 0 )]TJ/F20 11.9552 Tf 10.908 0 Td [(V P O .If x 2 V C 0 )]TJ/F20 11.9552 Tf 11.337 0 Td [(R ,then x= 2O asotherwise x )]TJ/F20 11.9552 Tf 7.084 -4.339 Td [(x + wouldbeahopin C 0 .ByLemma5.4, novertexin f a ` ;a r ;b ` ;b r g isin O .If b + 2 R ,then a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` b wastheedgeusedtoform C 00 andeither b + = b r or b ` b ++ wasahopin C 00 .Thus j R )-254(f a ` ;b ` ;a r ;b r gj 3unless a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` b )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` wasusedtoform C 00 .seeFigure5.6Thisimpliesthatunless a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` b )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` wasused toform C 00 j X C 0 )]TJ/F20 11.9552 Tf 11.955 0 Td [(V P Oj 1so,anysetoffourverticesin X C 0 )]TJ/F20 11.9552 Tf 12.166 0 Td [(V P has atleast7edgesto S 0 ,acontradiction.Soweassumethat a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` ;b )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` R andthusthe edge a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` b )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` wasusedtoform C 00 .Then j X C 0 )]TJ/F20 11.9552 Tf 11.955 0 Td [(V P Oj 2withequalityholding onlyif a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` and b )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` arebothin X C 0 .Thus,since a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` b )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` isanedgeof C 0 inthiscase, anysetoffourindependentverticesin X C 0 )]TJ/F20 11.9552 Tf 12.07 0 Td [(V P hasatleast7edgesto S 0 ,again acontradiction. Nowwenotethat C 0 hasachord.If ab 2 E G ,then ab isachordin C 0 .If a ` b ` isanedge,then C 0 containsatleastoneofthechords bb ` or aa ` .If a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` b a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` b ` ,or a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` ;b )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` isanedge,theneither C 0 hasachordoroneofthenets N bb ` b + ; P;b )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` ;b ++ N bb ` b + ; P;b \000 ` ;b ++ ,or N bb ` b + ; P;b )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` ;b +3 isinduceddependingonif b ` b \000 ` and/or b + b +3 areedges. Let P I = V P )-223(f a;b; g .Suppose a 1 orsimilarly b 1 istheendpointofachord a 1 a c .Then h a 1 ; a;a 2 ;a c i!f aa c g Nowweshow C 0 hasachord ht suchthat h + 2 X C 0 )]TJ/F20 11.9552 Tf 10.476 0 Td [(V P .Let h 0 t 0 beanychord of C 0 involvingneither a 1 nor b 1 .Since V P appearsconsecutivelyon C 0 ,wemay assumethat,withoutlossofgenerality, V P [ t 0 ;h 0 ] C 0 .If X C 0 h 0 ;t 0 C 0 = ; ,then Lemma5.2impliesthat G hasan s +1-cycle.Thusthereisaminimum i suchthat h 0 + i 2 X C 0 )]TJ/F20 11.9552 Tf 11.955 0 Td [(V P and,since h 0 + i )]TJ/F18 7.9701 Tf 6.586 0 Td [(1 = 2 X C 0 h 0 + i )]TJ/F18 7.9701 Tf 6.586 0 Td [(1 istheendpointofsomechord. 58

PAGE 69

Thus,let ht beachordsuchthat h + 2 X C 0 )]TJ/F20 11.9552 Tf 11.277 0 Td [(V P and,amongstallsuchchords assumethat ht isashortestchordseeFigure5.7.As C 0 ishop-free,theminimality of ht andtheclaw h t ; h;t + ;t )]TJ/F23 11.9552 Tf 7.085 -4.338 Td [(i thenimplythat ht + 2 E G .Thisfurtherimpliesthat dist C 0 t + ;h 3since ht + cannotbeahop.If ht doesnotskipatleast3verticesin X C 0 ,wearedonebyLemma5.2,solet h 1 ;h 2 ;h 3 2 X C 0 C 0 h;t appearinorderon C 0 Further,if h;t C 0 V P 6 = ; ,then h;t C 0 containsalltheinternalvertices of P h + ,andoneof a or b ,since V P appearsinorderand h + = 2 V P .Thus thenet N htt + ; h + h ++ h +3 h +4 ;t )]TJ/F20 11.9552 Tf 7.085 -4.338 Td [(;t +2 !f ht +2 g .Thisimpliesthat h h ; h + ;t;t +2 i is aninducedclawsince h + 2 X C 0 and tt +2 = 2 E G .Considernextthenet N = N htt + ; h + ;t )]TJ/F20 11.9552 Tf 7.085 -4.338 Td [(;t ++ t +3 t +4 t +5 .If h isadjacenttoanyvertex h 0 2f t ++ t +3 t +4 t +5 g then h h ; h + ;t;h 0 i!f th 0 g whichimpliesthat h 0 = t +5 sinceotherwise th 0 skips atmost2veticesin X C 0 .Ifanyvertex t 0 2f t )]TJ/F20 11.9552 Tf 7.085 -4.339 Td [(;t;t + g isadjacenttoanyvertex h 0 2f t ++ t +3 t +4 t +5 g ,thenonceagain h 0 = t +5 .Thusif N isnotinduced,thereisan edge t 0 h +5 where t 0 2f t )]TJ/F20 11.9552 Tf 7.084 -4.338 Td [(;t;t + g .If t +2 and t +4 arenoton P ,then f h 1 ;h 3 ;t +2 ;t +4 g is anindependantsetoffourverticeswithatleast7edgesto S 0 ,sosomevertexin S 0 isthecenterofaninduced K 1 ; 3 Thus t +2 t +3 ,and t +4 areallinternalverticesof P and,since ht + isanedge, a = t + byLemma5.2.However,if a = t + ,then b = t +7 ,andtheedge t 0 t +5 contradicts Lemma5.2. Lemma5.7requires s 6.Thefollowingobservationshowsthatif isatmost six,then s 6. Observation5.8. Ifthepath P = aI a a 0 b 0 I b b haslength2,3,4or5,then G hasa 6-cycle. Supposeforthesakeofcontradictionthat G hasno6-cycle,so s =5.The cycle C containsthevertices w x y ,and z ,whichallhavehops.Since s =5we know Q w = Q x = Q y = Q z .Thus G [ V C ]mustbecomplete,otherwiseby 59

PAGE 70

h h + = h 1 h 2 h 3 t )]TJET1 0 0 1 316.603 608.731 cmQ 1 0 0 1 7.397 -463.239 cmQ Q q Q q q 1 0 0 1 23.708 462.188 cm1.0 0.0 0.0 1.0 0.0 0.0 cm q 0 G 0 g 1 0 0 1 -347.708 -607.68 cmBT/F20 11.9552 Tf 347.708 607.68 Td [(t t + t +2 t +3 t +4 t +5 S 0 Figure5.7:Findinganinducedcopyof N ; 1 ; 1forLemma5.7. Wearguethatthereisanedgefromoneof t )]TJ/F15 11.9552 Tf 7.084 -4.338 Td [(, t ,or t + to t +5 which forceseachof t +2 t +3 ,and t +4 tohaveatleasttwoneighborsin S 0 Lemma5.4thevertex u 2 V C )-117(f w;x;y;z g mustbeboth a ` and a r .Since G [ V C ] isaclique, aPbCa haslength s + )]TJ/F15 11.9552 Tf 12.601 0 Td [(1andwecanskipanysubsetofverticesin V C )-222(f a;b g toobtaina6-cycle. 5.34-connected f K 1 ; 3 ;N ; 2 ; 2 g f K 1 ; 3 ;N ; 2 ; 2 g f K 1 ; 3 ;N ; 2 ; 2 g -freegraphsarepancyclic TogetherthelemmasinSection5.2provideaframeworkforshowinga f K 1 ; 3 ;N g freegraph G containingan s -cycle C containsan s +1-cycle.Theprooftechniquefor Theorem3.8consistsofconsideringaclawornetgivenby H .Since G is f K 1 ; 3 ;N g free, H isnotinduced.Weproceedbycaseanalysisshowingeachpossibleadjacency within H reachesacontradiction.WhenapplicableLemmas5.2and5.7providemany non-adjacenciessimplifyingthiscaseanalysis.ByObservation5.8ifthereisapath P = aI a a 0 b 0 I b b oflengthatmostve,then G hasa6-cycle.If P haslengthatmost ve,then G [ V C ]cannotbeaclique.Moreover,wheneveroneofthesepathshas length2,3or4,thereisavertexbetween Q a and Q b byLemma5.6. Inthissectionweprovethatif G is4-connectedand f K 1 ; 3 ;N ; 2 ; 2 g -freeand hasacycleoflength s ,where5 s j V G j)]TJ/F15 11.9552 Tf 18.177 0 Td [(1,thenitcontainsan s +1-cycle. SinceweshowedinLemma5.1thatsuchagraphhasa5-cycle,thiswillgivethe 60

PAGE 71

followinglemma. Lemma5.9. Every 4 -connected, f K 1 ; 3 ;N ; 2 ; 2 g -freegraphoforder n contains cyclesoflength s for 6 s n Proof: Weproceedbycontradictionandassumethat G isa4-connected, f K 1 ; 3 ;N ; 2 ; 2 g -freegraphcontainingacycle C oflength5 s n )]TJ/F15 11.9552 Tf 12.574 0 Td [(1,butno s +1-cycle.Thisproofisbrokenupintothreecasesbasedonhowmanyverticesof x 0 y 0 and z 0 arein V C .Severalclaimswillbeusedtoprovethatalargerinduced netexists.Recallthat I x = f x 1 ;:::;x p g I y = f y 1 ;:::;y q g ,and I z = f z 1 ;:::;z t g where j I x jj I y jj I z j Case1 Noneofthevertices x 0 y 0 and z 0 arein V C .seeFigure5.8 x x ` x r x 1 x p x 0 y y ` y r y 1 y q y 0 z z ` z r z 1 z t z 0 Figure5.8:Thecasewherenoneofthevertices x 0 y 0 ,or z 0 arein V C Case1.1 Suppose j I x j 2. If j I y j 2and j I z j 1,thenbyLemma5.2thenet N x 0 y 0 z 0 ; x p x p )]TJ/F18 7.9701 Tf 6.586 0 Td [(1 ;y q y q )]TJ/F18 7.9701 Tf 6.586 0 Td [(1 ;z t z t )]TJ/F18 7.9701 Tf 6.586 0 Td [(1 isaninducedcopyof N ; 2 ; 2.When j I y j 2and j I z j =0weseekavertex u thatis aneighborof z in V C thatisneither x nor y .If G [ V C ]isacliquethenclearlywe canndsucha u ,andwhen G [ V C ]isnotaclique u = z ` suces.ByLemma5.2 thenet N x 0 y 0 z 0 ; x p x p )]TJ/F18 7.9701 Tf 6.587 0 Td [(1 ;y q y q )]TJ/F18 7.9701 Tf 6.587 0 Td [(1 ;zu isaninducedcopyof N ; 2 ; 2. 61

PAGE 72

If j I y j = j I z j =1and yz 2 E G ,thenbyLemma5.7 G hasan s +1-cycle unless s =5.If s =5,then yzz 1 z 0 y 0 y 1 y isa6-cycleif yz 2 E G .Ineithercase G hasan s +1-cycleif yz 2 E G ,soweassume yz= 2 E G .However,thismeans thatthenet N x 0 y 0 z 0 ; x p x p )]TJ/F18 7.9701 Tf 6.587 0 Td [(1 ;y 1 y;z 1 z isinduced. Claim5.10. When x 0 y 0 ,and z 0 areallnotin V C and j I y j 1 and j I z j =0 ,the net N = N x 0 y 0 z 0 ; I x ;I y yy ` ;zz ` z )]TJ/F21 7.9701 Tf -0.533 -8.278 Td [(` isinduced. ByLemma5.4, y ` and z ` cannotbe x .ByLemma5.6 z )]TJ/F21 7.9701 Tf -0.532 -8.278 Td [(` 2 [ y r ;z ` ]whichimplies z )]TJ/F21 7.9701 Tf -0.533 -8.278 Td [(` isneither x nor y .ThereforebyLemma5.2thenet N x 0 y 0 z 0 ; I x ;I y yy ` ;zz ` z )]TJ/F21 7.9701 Tf -0.533 -8.278 Td [(` is inducedorthereisanedgebetween f y;y ` g and f z;z ` ;z )]TJ/F21 7.9701 Tf -0.533 -8.278 Td [(` g .Sincethepath yI y y 0 z 0 z haslengthatmostfourifanyofthepreviousedgesexistbyLemma5.7, G hasan s +1-cycle,acontradiction.Thus N isinduced. Case1.2 Suppose j I x j =1and j I y j =1. Considerthecasewhen j I z j =1.If xy xz ,or yz isanedge,then G hasan s +1-cyclebyLemma5.7.Otherwise N x 0 y 0 z 0 ; x 1 x;y 1 y;z 1 z isinduced. When j I z j =0thepath yy 1 y 0 z 0 z haslength4,sobyLemma5.6, z )]TJ/F21 7.9701 Tf -0.533 -8.278 Td [(` 2 [ y r ;z ` ] C Since G doesnothavean s +1-cycleLemma5.7impliesthat xy xz xz ` yz ,and yz ` arenotedges.Thusthenet N x 0 y 0 z 0 ; x 1 x;y 1 y;zz ` isinduced. Case1.3 Suppose j I x j 1and j I y j = j I z j =0. Weshowthisbyshowingthefollowingstrongerclaim. Claim5.11. When j I x j 1 and j I y j =0 thenet N = N x 0 y 0 z 0 ; I x xx ` x )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` ;yy ` y )]TJ/F21 7.9701 Tf -0.429 -8.278 Td [(` ;zz ` z )]TJ/F21 7.9701 Tf -0.533 -8.278 Td [(` isinduced. Fordistinct a;b 2f x;y;z g ,thepaths aI a a 0 b 0 I b b allhavelengthatmost4.Thus, since G doesnothavean s +1-cyclethereisnoedgebetween f x;x ` ;x )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` g f y;y ` ;y )]TJ/F21 7.9701 Tf -0.429 -8.278 Td [(` g and f z;z ` ;z )]TJ/F21 7.9701 Tf -0.533 -8.278 Td [(` g byLemma5.7.Therefore N isinduced. 62

PAGE 73

Case2 Thevertices x 0 and y 0 arenotin V C and z 0 isin V C Case2.1 Suppose j I x j 2. When j I y j 3and G [ V C ]isnotcompletethen N x 0 y 0 z ; x p x p )]TJ/F18 7.9701 Tf 6.586 0 Td [(1 ;y q y q )]TJ/F18 7.9701 Tf 6.586 0 Td [(1 ;z ` z )]TJ/F21 7.9701 Tf -0.533 -8.278 Td [(` is induced.When j I y j 4and G [ V C ]iscompletethen N x 0 y 0 z ; x p x p )]TJ/F18 7.9701 Tf 6.587 0 Td [(1 ;y q y q )]TJ/F18 7.9701 Tf 6.587 0 Td [(1 ;yy 1 isinduced.Noteif j I y j =3and G [ V C ]iscompletethen G hasan s +1-cycle. Claim5.12. When j I y j 2 thenet N = N x 0 y 0 z ; I x ;I y yy ` ;z ` z )]TJ/F21 7.9701 Tf -0.533 -8.278 Td [(` isinduced. Since G hasno s +1-cycle,byLemma5.7thereisnoedgebetween f y;y ` g and f z;z ` ;z )]TJ/F21 7.9701 Tf -0.532 -8.278 Td [(` g .Thus N isinduced. Case2.2 Suppose j I x j 1 Supposealsothat j I y j =1.Since G doesnothavean s +1-cycleby Lemma5.7thereisnoedgebetween f x g f y g ,and f z;z ` ;z )]TJ/F21 7.9701 Tf -0.533 -8.278 Td [(` g .Thusthenet N x 0 y 0 z ; x 1 x;y 1 y;z ` z )]TJ/F21 7.9701 Tf -0.533 -8.278 Td [(` isinduced. Claim5.13. When j I x j 1 and j I y j =0 thenet N = N x 0 y 0 z ; I x x ` x )]TJ/F21 7.9701 Tf 0 -8.277 Td [(` ;yy ` y )]TJ/F21 7.9701 Tf -0.429 -8.277 Td [(` ;z ` z )]TJ/F21 7.9701 Tf -0.533 -8.278 Td [(` isinduced. Fordistinct a;b 2f x;y;z g ,thepath aI a a 0 bb 0 I b b haslengthatmost4.By Lemma5.6thevertices a ` a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` existandaredistinctforall a 2f x;y;z g .Since N isnotinduced,fordistinct a;b 2f x;y;z g thereissomeedgebetween a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` ;a ` ;a and b )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` ;b ` ;b .ByLemma5.7 G hasan s +1-cycleunlesseither xz or yz issuch anedge.If xz isanedge,then h z ; y 0 ;x;z ` i!f xy 0 g andif yz isanedge,then h z ; x 0 ;y;z ` i!f yx 0 g ,ineithercase F isnotminimal.Thus N isinduced. Case3 Thevertices y 0 and z 0 areon C Lemma5.2doesnotapplyinthiscase.Suppose j I x j > 0and x i 2 I x .If x i y is anedge,then h y ; z;x i ;y ` i forcesanedgewhicheithercreatesan s +1-cycleora shorterfan.Replacing y with z inthepreviousargumentimpliestherearenoedges between I x and f y;z g .Anedgebetween I x [f v g )-175(f x 1 g and V C )-175(f y;z g implies 63

PAGE 74

thereexistsashorterfan.ThereforebyLemma5.14followingwhen j I x j > 0 G has aninduced N ; 2 ; 2. When j I x j =0weshowthereisaninduced N ; 2 ; 2.Firstconsider N x 0 yz ; xx ` ;y ` y )]TJ/F21 7.9701 Tf -0.429 -8.278 Td [(` ;z ` z )]TJ/F21 7.9701 Tf -0.533 -8.278 Td [(` .Sincethisnetisnotinduced,thereisanedgebetweentwoof f x;x ` g y;y ` ;y )]TJ/F21 7.9701 Tf -0.429 -8.277 Td [(` ,and z;z ` ;z )]TJ/F21 7.9701 Tf -0.533 -8.277 Td [(` .Unlessthatedgeiseither xy or xz ,thevertex x 0 canbeaddedtothecycletoforman s +1-cycle.Since y ` x 0 yCx ` x + Cy ` isan s +1cycle,if xy isanedgethen h y ; y ` ;x;z i forcestheedge xz .Similarly,if xz isanedge then h z ; z ` ;x;y i forcestheedge xz .Thusconsiderthenet N xyz ; x ` x )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` ;y ` y )]TJ/F21 7.9701 Tf -0.429 -8.278 Td [(` ;z ` z )]TJ/F21 7.9701 Tf -0.533 -8.278 Td [(` whichisaninducedcopyof N ; 2 ; 2unless G hasan s +1-cycle.. Lemma5.14. Suppose y 0 = y and z 0 = z .Let u 2 V C beavertexwherethereis aninduced u )]TJ/F20 11.9552 Tf 12.163 0 Td [(v -path P = vu k :::u 1 u whoseinternalverticesareallo V C .If thelengthof P isatleast2andtherearenoedgesbetween f u 2 ;:::;u k g and V C then G containsaninduced N ; 2 ; 2 Proof: Dene I u = f u 1 ;:::;u k g .ByLemma5.6, G [ V C ]isnotacliquesince yvz haslength2.Since G hasno s +1-cycletherearenoedgesbetween f y;y ` ;y )]TJ/F21 7.9701 Tf -0.429 -8.278 Td [(` g and f z;z ` ;z )]TJ/F21 7.9701 Tf -0.533 -8.278 Td [(` g Firstweshowthatif j I x j 3then u 1 isnotadjacentto f u ` ;u )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` ;y ` ;y )]TJ/F21 7.9701 Tf -0.429 -8.278 Td [(` ;z ` ;z )]TJ/F21 7.9701 Tf -0.533 -8.278 Td [(` g ByLemma5.4 a ` isnotadjacentto u 1 for a 2f x;y;z g .If u 1 u )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` isanedgethen G immediatelyhasan s +1-cycle.Suppose u 1 a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` isanedgefor a 2f y;z g .Then thecycle a )]TJ/F21 7.9701 Tf 0 -8.277 Td [(` I u vyC )]TJ/F20 11.9552 Tf 7.085 -4.339 Td [(a ` a + Ca )]TJ/F21 7.9701 Tf 0 -8.277 Td [(` isan s + j I u j -cycle.Wecanskipanyofthevertices f a ` ;w;x;y;z g)-222(f a;a )]TJ/F21 7.9701 Tf 0 -8.278 Td [(` g toforman s +1-cycle. Therefore,when j I u j 3thenet N vyz ; u k u k )]TJ/F18 7.9701 Tf 6.586 0 Td [(1 u k )]TJ/F18 7.9701 Tf 6.586 0 Td [(2 ;y ` y )]TJ/F21 7.9701 Tf -0.429 -8.278 Td [(` ;z ` z )]TJ/F21 7.9701 Tf -0.533 -8.278 Td [(` isinduced.Note thatwhen j I u j =3impliesthat u 1 isnotadjacentto f y ` ;y )]TJ/F21 7.9701 Tf -0.429 -8.278 Td [(` ;z ` ;z )]TJ/F21 7.9701 Tf -0.533 -8.278 Td [(` g ,andsince j I u j > 0 u 1 isnotadjacentto y or z When j I u j2f 1 ; 2 g considerthenet N vyz ; I u uu ` ;y ` y )]TJ/F21 7.9701 Tf -0.429 -8.278 Td [(` ;z ` z )]TJ/F21 7.9701 Tf -0.533 -8.278 Td [(` .Lemma5.7implies thatthenetisinduced. 64

PAGE 75

6.2-factorsinHamiltonianGraphs 6.1Introduction RecallthatBondyshowedthefollowing. Theorem2.15. If G isagraphoforder n 3 withminimumdegree n 2 ,then G iseitherpancyclicor G isisomorphicto K n 2 ; n 2 In[2]Amaretal.provedthattheminimumdegreethresholdforpancyclicityin Theorem2.15canbesignicantlyloweredinnecessarilynonbipartitehamiltonian graphs. Theorem6.1. If G isahamiltoniangraphoforder n andand G 2 n +1 5 ,then G iseitherpancyclicorbipartite. Similarimprovementstoestablishedsucientconditionsfortheexistenceofsome cycle-structuralpropertyhavebeenfoundonanumberofoccasionsbyrestrictingto theclassofhamiltoniangraphs.Forinstance,motivatedbyTheorems6.1and2.21, Faudreeetal.provedthefollowingresultin[26]. Theorem6.2. If G isahamiltoniangraphoforder n 6 and G 5 12 n +2 ,then G containsa2-factorwithtwocomponents. WithTheorems2.20and6.2inmind,Pfender[56]showedthefollowingresulton claw-freegraphs. Theorem6.3. If G isaclaw-freehamiltoniangraphoforder n 6 and G 7 then G containsa2-factorwithtwocomponents. Theorem6.2inspiredthefollowingconjecture,whichalsoappearedin[26]. Conjecture6.4. Foreachinteger k 2 thereexistsapositiverealnumber c k < 1 2 andintegers a k and n k suchthateveryhamiltoniangraph G oforder n>n k with G c k n + a k containsa2-factorwith k cycles. 65

PAGE 76

Conjecture6.4wasarmedbySarkozy[64]usingtheregularity{blow-upmethod. Theorem6.5. Thereexistsarealnumber "> 0 suchthatforeveryinteger k 2 thereexistsaninteger n 0 = n 0 k suchthateveryhamiltoniangraph G oforder n n 0 with G = 2 )]TJ/F20 11.9552 Tf 11.955 0 Td [(" n hasa2-factorwith k components. Sarkozy'sresultraisesanaturalquestion:whatistheminimum = k;n such thateveryhamiltoniangraphoforder n withminimumdegreeatleast hasa2factorwithexactly k cycles?In2012,Gy}oriandLiannounced[42]thattheyhad shown )]TJ/F18 7.9701 Tf 8.792 -4.976 Td [(5 11 + n sucesfor n sucientlylarge.Ourmainresultisthefollowing improvementofTheorem6.2,Theorem6.5,andthatresult. Theorem6.6. Let k 1 and 0 <"< 1 10 .If G isahamiltoniangraphon n 3 k verticeswith G )]TJ/F18 7.9701 Tf 6.675 -4.976 Td [(2 5 + n ,then G containsa 2 -factorwithexactly k cycles. Additionally,ourproofusesonlyelementarytechniques,andhencerequiresa signicantlysmallerboundon n thanthatrequiredbyTheorem6.5. OnevexingaspectofConjecture6.4andtherelatedworkdescribedhereisthat itispossiblethatasublinear,orevenconstant,minimumdegreewouldsuceto ensureahamiltoniangraphhasa2-factorofthedesiredtype.Specically,whilethe 4-regulargraphobtainedbyreplacingeveryvertexofacyclewithacopyof K 5 )]TJ/F20 11.9552 Tf 12.168 0 Td [(e isanexampleofafamilyofhamiltoniangraphsthatdonotcontaina2-factorwith twocycles,currentlyweknowofnoexamplethathas 5. 6.2ProofofTheorem6.6 AkeyingredientinourproofisthefollowinglemmaofNash-Williams[53].For completeness,weprovideabriefsketchoftheproofusingmodernterminology. Lemma6.7. Let G bea 2 -connectedgraphon n vertices.If G =: d n +2 3 ,then either G hasahamiltoniancycleor G d +1 66

PAGE 77

Proof: Choosealongestcycle C in G ,whichhaslengthatleastmin f 2 G ; j G jg byaclassicalresultofDirac[16].Ifsomecomponentof G )]TJ/F20 11.9552 Tf 12.391 0 Td [(C isavertex v ,then thesuccessorsoftheneighborsof v on C alongwith v formanindependentset ofsizeatleast d +1.Otherwise,let P bealongestpathin G )]TJ/F20 11.9552 Tf 12.813 0 Td [(C andsuppose that P haslengthatleast1.Considertheendpointsof P say x 1 and x p ;allof theirneighborsarein V P [ V C .If v i 2 V C isaneighborof x 1 ,then x p cannotbeadjacenttoanyofthe p verticessucceeding v i .Thusfor i 2f 1 ;p g ,let X i = f u + j j v 2 N x i V C ; 0 j p g .If X 1 X p 6 = ; ,then C canbeextended along P whileskippingatmost p )]TJ/F15 11.9552 Tf 11.819 0 Td [(1verticesof C .Now j X i j 2 j N C x i j + p )]TJ/F15 11.9552 Tf 11.818 0 Td [(2so j X 1 [ X p j 4 d )]TJ/F20 11.9552 Tf 11.997 0 Td [(p +1+2 p )]TJ/F15 11.9552 Tf 11.997 0 Td [(4whichimpliesthat4 d )]TJ/F15 11.9552 Tf 11.996 0 Td [(2 p j V C j n )]TJ/F20 11.9552 Tf 11.997 0 Td [(p and thus p n +8 3 .Ontheotherhand, p n )-236(j C j n )]TJ/F18 7.9701 Tf 6.586 0 Td [(4 3 ,acontradiction.Therefore C isahamiltoniancycle. WealsoneedthefollowingwellknownresultofPosa[58]. Theorem6.8. Let G beagraphon n verticesandforall i 2 [ n ] let S i = f v 2 V G :deg v i g .Ifforall 1 i< n )]TJ/F18 7.9701 Tf 6.587 0 Td [(1 2 j S i j k )]TJ/F15 11.9552 Tf 11.956 0 Td [(1 n ,then G contains k pairwisenon-intersectingedges. Proof: Following[28]Let v 0 ;v 1 ;:::v n )]TJ/F18 7.9701 Tf 6.586 0 Td [(1 betheverticesof G givenintheorder theyappearalongtheconvexhullof G andlet K G bethecompletegraphon V G Wepartitiontheedgesof K G into n setsdenotedby E i;j with i 2 0 ; 1 ;:::; b n )]TJ/F18 7.9701 Tf 6.586 0 Td [(1 2 c and j 2f 1 ; 2 g suchthat E i;j = xy j 0 r b n 2 c)]TJ/F15 11.9552 Tf 19.925 0 Td [(1 ;x = v i + r ;y = v i )]TJ/F21 7.9701 Tf 6.587 0 Td [(j )]TJ/F21 7.9701 Tf 6.586 0 Td [(r indices 67

PAGE 78

takenmod n andif n isoddcalltheremainingedges E n +1 2 ; 1 .seeFigure6.1Now, ifthereare k edgesin G inany E i;j ,then G contains k pairwisenon-intersecting edges,thuseach E i;j containsatmost k )]TJ/F15 11.9552 Tf 11.015 0 Td [(1edgesof G andso G hasatmost k )]TJ/F15 11.9552 Tf 11.015 0 Td [(1 n edges.However, j E G j > k )]TJ/F15 11.9552 Tf 12.223 0 Td [(1 n establishingthat G containsatleast k pairwise non-intersectingedges. an=8 bn=9 E 1 ; 1 E 1 ; 2 v 0 v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 0 v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 Figure6.1: E 1 ;j foragraphofevenorderaandagraphofodd orderb. WearenowreadytoproveTheorem6.6. Proof: Let k 2,0 <"< 1 10 ,and n 3 k .Notethatthisimplies k 1 3 "n .We considertwocases,basedontheconnectivityof G Case1: G <"n Let S beaminimumcut-setof G .As G ishamiltonian,wehave2 j S j <"n and further,since G )]TJ/F20 11.9552 Tf 12.083 0 Td [(S )]TJ/F18 7.9701 Tf 6.675 -4.977 Td [(2 5 + n )-233(j S j > 2 5 n G )]TJ/F20 11.9552 Tf 12.083 0 Td [(S hasexactlytwocomponents. Let X and Y bethosetwocomponents,andsupposewithoutlossofgeneralitythat j X jj Y j .Notethenthat 2 5 n< j Y j n 2 j X j < 3 5 n: .1 Consequently,eachpairofadjacentvertices u and v in Y satises j N u N v Y j 4 5 n )-75(j Y j 4 5 j Y j )-75(j Y j = 3 5 j Y j .Sowemayremoveafamily T of k )]TJ/F15 11.9552 Tf 10.199 0 Td [(2vertex-disjoint 68

PAGE 79

trianglesfrom Y andset Y 0 = Y )]TJ/F26 11.9552 Tf 11.955 8.966 Td [(S T 2T V T Now,let X = f v 2 S :deg v;X >"n g Y = S )]TJ/F20 11.9552 Tf 12.262 0 Td [(X G 1 = G [ X [ X ],and G 2 = G [ Y 0 [ Y ].Wenowverifythat G 1 and G 2 satisfytheconditionsofTheorem 6.8,inwhichcasethehamiltoniancyclesin G 1 and G 2 alongwith T giveusthe desired2-factorwith k cycles. Firstnotethatby.1, j X [ X j n 2 so j Y 0 [ Y j n 2 .Nowforall y 2 Y deg y;G 2 2 5 + n )]TJ/F15 11.9552 Tf 11.955 0 Td [(deg y;X )-222(j S j)-222(j Y )]TJ/F20 11.9552 Tf 11.955 0 Td [(Y 0 j 2 5 )]TJ/F15 11.9552 Tf 11.955 0 Td [(2 n n 5 > j Y j ; andforall y 2 Y 0 deg y;G 2 2 5 + n )-222(j X j 2 5 n 2 5 j Y 0 [ Y j 4 5 j Y 0 [ Y j : Thesecalculationsshowthat S i = ; forall i< n 5 and j S i j < n 5 i forall n 5 i j Y 0 [ Y j 2 Likewise,by.1, j Y j > 2 n 5 andthus j X [ X j < 3 5 n .Nowforall x 2 X deg x;G 1 >"n> j X j andforall x 2 X deg x;G 1 2 5 + n )-222(j Y j 2 5 n 2 5 5 3 j X [ X j = 2 3 j X [ X j : Thesecalculationsshowthat S i = ; forall i<"n and j S i j <"n i forall "n i j X 0 [ X j 2 Case2: G "n Supposerstthat G < 2 n 5 ,andlet x 1 ;:::;x k )]TJ/F18 7.9701 Tf 6.586 0 Td [(1 bedistinctverticesin V G Since )]TJ/F18 7.9701 Tf 6.675 -4.976 Td [(2 5 + n )]TJ/F15 11.9552 Tf 11.046 0 Td [(3 k )]TJ/F15 11.9552 Tf 11.046 0 Td [(1 > 2 n 5 > G ,wecaniterativelyconstructafamilyof k )]TJ/F15 11.9552 Tf 11.046 0 Td [(1 69

PAGE 80

vertexdisjointtriangleseachconsistingof x i andsomeedgein N x i .Let G 0 bethe graphobtainedbydeletingthese k )]TJ/F15 11.9552 Tf 11.955 0 Td [(1triangles.As G 0 2 5 + n )]TJ/F15 11.9552 Tf 11.955 0 Td [(3 k )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 > 2 n 5 > G G 0 ; and G 0 2,Lemma6.7impliesthat G 0 ishamiltonian,completingthedesired 2-factorwith k cycles. Therefore,wemayassumethat G 2 n 5 .Let H beahamiltoniancyclein G andlet X = f x 1 ;x 2 ;:::;x t g bealargestindependentsetin G .Assumingthat H has animplicitclockwiseorientation,foreach i 2 [ t ],let y i bethesuccessorof x i along H andlet Y = f y 1 ;y 2 ;:::;y t g .Notethatsince X isindependent, X Y = ; aThehamiltoniancycle H withverticesfrom X coloredwhiteand verticesfrom Y colored black bTheauxiliarydirectedgraph D cTheauxiliaryconvex geometricgraph)]TJET1 0 0 1 401.953 296.92 cmQ 1 0 0 1 -77.953 13.067 cmQ Q q 0.99628 w 0 G 0 g -141.73404 85.04042 m -79.37114 85.04042 m -79.37114 119.48294 -107.29153 147.40334 -141.73404 147.40334 c -176.17656 147.40334 -204.09695 119.48294 -204.09695 85.04042 c -204.09695 50.5979 -176.17656 22.67752 -141.73404 22.67752 c -107.29153 22.67752 -79.37114 50.5979 -79.37114 85.04042 c h -141.73404 85.04042 m S Q q Q q Q q Q q Q q Q q Q q Q q Q q Q q Q q Q q Q q Q q Q q Q q Q q 0.99628 w 0 G 0 g -93.96196 125.12672 m -164.08284 26.81995 l -100.81985 132.1066 m -172.91527 31.03244 l S Q q 0.34 g 0.99628 w 0 G 0 g 1 g -82.76831 105.34418 m -79.93346 105.34418 m -79.93346 106.90984 -81.20265 108.17903 -82.76831 108.17903 c -84.33395 108.17903 -85.60315 106.90984 -85.60315 105.34418 c -85.60315 103.77853 -84.33395 102.50934 -82.76831 102.50934 c -81.20265 102.50934 -79.93346 103.77853 -79.93346 105.34418 c h -82.76831 105.34418 m B Q q 0.34 g 0.99628 w 0 G 0 g 0 g -80.31798 95.869 m -77.48312 95.869 m -77.48312 97.43466 -78.75232 98.70386 -80.31798 98.70386 c -81.88362 98.70386 -83.15282 97.43466 -83.15282 95.869 c -83.15282 94.30334 -81.88362 93.03415 -80.31798 93.03415 c -78.75232 93.03415 -77.48312 94.30334 -77.48312 95.869 c h -80.31798 95.869 m B Q q 0.34 g 0.99628 w 0 G 0 g 1 g -100.81985 132.1066 m -97.985 132.1066 m -97.985 133.67226 -99.2542 134.94145 -100.81985 134.94145 c -102.3855 134.94145 -103.6547 133.67226 -103.6547 132.1066 c -103.6547 130.54094 -102.3855 129.27174 -100.81985 129.27174 c -99.2542 129.27174 -97.985 130.54094 -97.985 132.1066 c h -100.81985 132.1066 m B Q q 0.34 g 0.99628 w 0 G 0 g 0 g -93.96196 125.12672 m -91.1271 125.12672 m -91.1271 126.69238 -92.39632 127.96158 -93.96196 127.96158 c -95.52762 127.96158 -96.79681 126.69238 -96.79681 125.12672 c -96.79681 123.56108 -95.52762 122.29189 -93.96196 122.29189 c -92.39632 122.29189 -91.1271 123.56108 -91.1271 125.12672 c h -93.96196 125.12672 m B Q q 0.34 g 0.99628 w 0 G 0 g 1 g -129.83493 146.2575 m -127.00009 146.2575 m -127.00009 147.82317 -128.26929 149.09236 -129.83493 149.09236 c -131.40059 149.09236 -132.66978 147.82317 -132.66978 146.2575 c -132.66978 144.69186 -131.40059 143.42267 -129.83493 143.42267 c -128.26929 143.42267 -127.00009 144.69186 -127.00009 146.2575 c h -129.83493 146.2575 m B Q q 0.34 g 0.99628 w 0 G 0 g 0 g -120.40474 143.6424 m -117.56989 143.6424 m -117.56989 145.20804 -118.83908 146.47723 -120.40474 146.47723 c -121.9704 146.47723 -123.2396 145.20804 -123.2396 143.6424 c -123.2396 142.07674 -121.9704 140.80754 -120.40474 140.80754 c -118.83908 140.80754 -117.56989 142.07674 -117.56989 143.6424 c h -120.40474 143.6424 m B Q q 0.34 g 0.99628 w 0 G 0 g 1 g -195.1888 117.15982 m -192.35396 117.15982 m -192.35396 118.72546 -193.62315 119.99466 -195.1888 119.99466 c -196.75446 119.99466 -198.02365 118.72546 -198.02365 117.15982 c -198.02365 115.59416 -196.75446 114.32497 -195.1888 114.32497 c -193.62315 114.32497 -192.35396 115.59416 -192.35396 117.15982 c h -195.1888 117.15982 m B Q q 0.34 g 0.99628 w 0 G 0 g 0 g -189.50612 125.12672 m -186.67126 125.12672 m -186.67126 126.69238 -187.94048 127.96158 -189.50612 127.96158 c -191.07178 127.96158 -192.34097 126.69238 -192.34097 125.12672 c -192.34097 123.56108 -191.07178 122.29189 -189.50612 122.29189 c -187.94048 122.29189 -186.67126 123.56108 -186.67126 125.12672 c h -189.50612 125.12672 m B Q q 0.34 g 0.99628 w 0 G 0 g 1 g -190.19905 45.79453 m -187.36421 45.79453 m -187.36421 47.36017 -188.6334 48.62938 -190.19905 48.62938 c -191.76471 48.62938 -193.0339 47.36017 -193.0339 45.79453 c -193.0339 44.22887 -191.76471 42.95967 -190.19905 42.95967 c -188.6334 42.95967 -187.36421 44.22887 -187.36421 45.79453 c h -190.19905 45.79453 m B Q q 0.34 g 0.99628 w 0 G 0 g 0 g -195.74202 53.8592 m -192.90717 53.8592 m -192.90717 55.42485 -194.17636 56.69405 -195.74202 56.69405 c -197.30768 56.69405 -198.57687 55.42485 -198.57687 53.8592 c -198.57687 52.29355 -197.30768 51.02435 -195.74202 51.02435 c -194.17636 51.02435 -192.90717 52.29355 -192.90717 53.8592 c h -195.74202 53.8592 m B Q q 0.34 g 0.99628 w 0 G 0 g 1 g -164.08284 26.81995 m -161.24799 26.81995 m -161.24799 28.3856 -162.51718 29.6548 -164.08284 29.6548 c -165.64848 29.6548 -166.91768 28.3856 -166.91768 26.81995 c -166.91768 25.25429 -165.64848 23.98509 -164.08284 23.98509 c -162.51718 23.98509 -161.24799 25.25429 -161.24799 26.81995 c h -164.08284 26.81995 m B Q q 0.34 g 0.99628 w 0 G 0 g 0 g -172.91527 31.03244 m -170.08041 31.03244 m -170.08041 32.5981 -171.34961 33.8673 -172.91527 33.8673 c -174.48091 33.8673 -175.7501 32.5981 -175.7501 31.03244 c -175.7501 29.4668 -174.48091 28.1976 -172.91527 28.1976 c -171.34961 28.1976 -170.08041 29.4668 -170.08041 31.03244 c h -172.91527 31.03244 m B Q q 0.34 g 0.99628 w 0 G 0 g 1 g -111.49965 30.49695 m -108.6648 30.49695 m -108.6648 32.0626 -109.93399 33.3318 -111.49965 33.3318 c -113.06529 33.3318 -114.3345 32.0626 -114.3345 30.49695 c -114.3345 28.9313 -113.06529 27.66211 -111.49965 27.66211 c -109.93399 27.66211 -108.6648 28.9313 -108.6648 30.49695 c h -111.49965 30.49695 m B Q q 0.34 g 0.99628 w 0 G 0 g 0 g -120.40474 26.43845 m -117.56989 26.43845 m -117.56989 28.0041 -118.83908 29.2733 -120.40474 29.2733 c -121.9704 29.2733 -123.2396 28.0041 -123.2396 26.43845 c -123.2396 24.8728 -121.9704 23.6036 -120.40474 23.6036 c -118.83908 23.6036 -117.56989 24.8728 -117.56989 26.43845 c h -120.40474 26.43845 m B Q q 0.34 g 0.99628 w 0 G 0 g 1 g -80.51695 73.14131 m -77.6821 73.14131 m -77.6821 74.70697 -78.9513 75.97617 -80.51695 75.97617 c -82.0826 75.97617 -83.3518 74.70697 -83.3518 73.14131 c -83.3518 71.57567 -82.0826 70.30647 -80.51695 70.30647 c -78.9513 70.30647 -77.6821 71.57567 -77.6821 73.14131 c h -80.51695 73.14131 m B Q q 0.34 g 0.99628 w 0 G 0 g 0 g -83.13206 63.71112 m -80.29723 63.71112 m -80.29723 65.27676 -81.56642 66.54597 -83.13206 66.54597 c -84.69772 66.54597 -85.96692 65.27676 -85.96692 63.71112 c -85.96692 62.14546 -84.69772 60.87627 -83.13206 60.87627 c -81.56642 60.87627 -80.29723 62.14546 -80.29723 63.71112 c h -83.13206 63.71112 m B Q q Q q Q q Q q Q q Q q Q q Q q Q q 0.99628 w 0 G 0 g 38.61775 124.72092 m 4.96252 101.59073 -10.84088 73.95367 -22.73912 40.35286 c S q -0.33423 -0.94385 0.94385 -0.33423 -22.73912 40.35286 cm q 5.20058 0.0 m 3.65962 0.28891 1.15567 1.15567 -0.57784 2.1669 c -0.57784 -2.1669 l 1.15567 -1.15567 3.65962 -0.28891 5.20058 0.0 c f Q Q Q q 0.99628 w 0 G 0 g -21.78444 33.7295 m 7.3525 62.36203 23.83636 85.47157 39.174 117.62823 c S q 0.43166 0.90501 -0.90501 0.43166 39.174 117.62823 cm q 5.20058 0.0 m 3.65962 0.28891 1.15567 1.15567 -0.57784 2.1669 c -0.57784 -2.1669 l 1.15567 -1.15567 3.65962 -0.28891 5.20058 0.0 c f Q Q Q q 0.34 g 0.99628 w 0 G 0 g 0.34 g 60.37407 100.65373 m 63.20892 100.65373 m 63.20892 102.21939 61.93973 103.48859 60.37407 103.48859 c 58.80843 103.48859 57.53922 102.21939 57.53922 100.65373 c 57.53922 99.08809 58.80843 97.81888 60.37407 97.81888 c 61.93973 97.81888 63.20892 99.08809 63.20892 100.65373 c h 60.37407 100.65373 m B Q q 0.34 g 0.99628 w 0 G 0 g 0.34 g 44.47786 128.74837 m 47.31271 128.74837 m 47.31271 130.31403 46.04352 131.58322 44.47786 131.58322 c 42.91222 131.58322 41.64302 130.31403 41.64302 128.74837 c 41.64302 127.18272 42.91222 125.91353 44.47786 125.91353 c 46.04352 125.91353 47.31271 127.18272 47.31271 128.74837 c h 44.47786 128.74837 m B Q q 0.34 g 0.99628 w 0 G 0 g 0.34 g 16.66481 145.13162 m 19.49966 145.13162 m 19.49966 146.69728 18.23047 147.96648 16.66481 147.96648 c 15.09917 147.96648 13.82996 146.69728 13.82996 145.13162 c 13.82996 143.56596 15.09917 142.29677 16.66481 142.29677 c 18.23047 142.29677 19.49966 143.56596 19.49966 145.13162 c h 16.66481 145.13162 m B Q q 0.34 g 0.99628 w 0 G 0 g 0.34 g -50.7687 121.25249 m -47.93385 121.25249 m -47.93385 122.81815 -49.20305 124.08734 -50.7687 124.08734 c -52.33435 124.08734 -53.60355 122.81815 -53.60355 121.25249 c -53.60355 119.68684 -52.33435 118.41765 -50.7687 118.41765 c -49.20305 118.41765 -47.93385 119.68684 -47.93385 121.25249 c h -50.7687 121.25249 m B Q q 0.34 g 0.99628 w 0 G 0 g 0.34 g -51.39285 49.71982 m -48.558 49.71982 m -48.558 51.28546 -49.8272 52.55466 -51.39285 52.55466 c -52.9585 52.55466 -54.22769 51.28546 -54.22769 49.71982 c -54.22769 48.15416 -52.9585 46.88496 -51.39285 46.88496 c -49.8272 46.88496 -48.558 48.15416 -48.558 49.71982 c h -51.39285 49.71982 m B Q q 0.34 g 0.99628 w 0 G 0 g 0.34 g -26.84589 28.75555 m -24.01103 28.75555 m -24.01103 30.3212 -25.28023 31.59041 -26.84589 31.59041 c -28.41153 31.59041 -29.68073 30.3212 -29.68073 28.75555 c -29.68073 27.1899 -28.41153 25.9207 -26.84589 25.9207 c -25.28023 25.9207 -24.01103 27.1899 -24.01103 28.75555 c h -26.84589 28.75555 m B Q q 0.34 g 0.99628 w 0 G 0 g 0.34 g 25.86014 28.2949 m 28.69499 28.2949 m 28.69499 29.86055 27.4258 31.12975 25.86014 31.12975 c 24.29448 31.12975 23.02528 29.86055 23.02528 28.2949 c 23.02528 26.72925 24.29448 25.46005 25.86014 25.46005 c 27.4258 25.46005 28.69499 26.72925 28.69499 28.2949 c h 25.86014 28.2949 m B Q q 0.34 g 0.99628 w 0 G 0 g 0.34 g 60.09119 68.37561 m 62.92604 68.37561 m 62.92604 69.94125 61.65685 71.21045 60.09119 71.21045 c 58.52554 71.21045 57.25635 69.94125 57.25635 68.37561 c 57.25635 66.80995 58.52554 65.54076 60.09119 65.54076 c 61.65685 65.54076 62.92604 66.80995 62.92604 68.37561 c h 60.09119 68.37561 m B Q q Q q Q q Q q Q q Q q Q q Q q Q q 0.99628 w 0 G 0 g 186.21191 128.74837 m 114.88815 28.75555 l S Q q 0.99628 w 0 G 0 g [ 2.98883 2.98883 ] 0.0 d 202.10812 100.65373 m 186.21191 128.74837 l S Q q 0.99628 w 0 G 0 g [ 2.98883 2.98883 ] 0.0 d 186.21191 128.74837 m 158.39886 145.13162 l S Q q 0.99628 w 0 G 0 g [ 2.98883 2.98883 ] 0.0 d 158.39886 145.13162 m 90.96533 121.25249 l S Q q 0.99628 w 0 G 0 g [ 2.98883 2.98883 ] 0.0 d 90.96533 121.25249 m 90.34119 49.71982 l S Q q 0.99628 w 0 G 0 g [ 2.98883 2.98883 ] 0.0 d 90.34119 49.71982 m 114.88815 28.75555 l S Q q 0.99628 w 0 G 0 g [ 2.98883 2.98883 ] 0.0 d 114.88815 28.75555 m 167.5942 28.2949 l S Q q 0.99628 w 0 G 0 g [ 2.98883 2.98883 ] 0.0 d 167.5942 28.2949 m 201.82524 68.37561 l S Q q 0.99628 w 0 G 0 g [ 2.98883 2.98883 ] 0.0 d 201.82524 68.37561 m 202.10812 100.65373 l S Q q 0.34 g 0.99628 w 0 G 0 g 0.34 g 202.10812 100.65373 m 204.94298 100.65373 m 204.94298 102.21939 203.67377 103.48859 202.10812 103.48859 c 200.54247 103.48859 199.27327 102.21939 199.27327 100.65373 c 199.27327 99.08809 200.54247 97.81888 202.10812 97.81888 c 203.67377 97.81888 204.94298 99.08809 204.94298 100.65373 c h 202.10812 100.65373 m B Q q 0.34 g 0.99628 w 0 G 0 g 0.34 g 186.21191 128.74837 m 189.04677 128.74837 m 189.04677 130.31403 187.77757 131.58322 186.21191 131.58322 c 184.64626 131.58322 183.37706 130.31403 183.37706 128.74837 c 183.37706 127.18272 184.64626 125.91353 186.21191 125.91353 c 187.77757 125.91353 189.04677 127.18272 189.04677 128.74837 c h 186.21191 128.74837 m B Q q 0.34 g 0.99628 w 0 G 0 g 0.34 g 158.39886 145.13162 m 161.2337 145.13162 m 161.2337 146.69728 159.96451 147.96648 158.39886 147.96648 c 156.8332 147.96648 155.56401 146.69728 155.56401 145.13162 c 155.56401 143.56596 156.8332 142.29677 158.39886 142.29677 c 159.96451 142.29677 161.2337 143.56596 161.2337 145.13162 c h 158.39886 145.13162 m B Q q 0.34 g 0.99628 w 0 G 0 g 0.34 g 90.96533 121.25249 m 93.80019 121.25249 m 93.80019 122.81815 92.53099 124.08734 90.96533 124.08734 c 89.39967 124.08734 88.13048 122.81815 88.13048 121.25249 c 88.13048 119.68684 89.39967 118.41765 90.96533 118.41765 c 92.53099 118.41765 93.80019 119.68684 93.80019 121.25249 c h 90.96533 121.25249 m B Q q 0.34 g 0.99628 w 0 G 0 g 0.34 g 90.34119 49.71982 m 93.17604 49.71982 m 93.17604 51.28546 91.90683 52.55466 90.34119 52.55466 c 88.77553 52.55466 87.50633 51.28546 87.50633 49.71982 c 87.50633 48.15416 88.77553 46.88496 90.34119 46.88496 c 91.90683 46.88496 93.17604 48.15416 93.17604 49.71982 c h 90.34119 49.71982 m B Q q 0.34 g 0.99628 w 0 G 0 g 0.34 g 114.88815 28.75555 m 117.723 28.75555 m 117.723 30.3212 116.45381 31.59041 114.88815 31.59041 c 113.3225 31.59041 112.0533 30.3212 112.0533 28.75555 c 112.0533 27.1899 113.3225 25.9207 114.88815 25.9207 c 116.45381 25.9207 117.723 27.1899 117.723 28.75555 c h 114.88815 28.75555 m B Q q 0.34 g 0.99628 w 0 G 0 g 0.34 g 167.5942 28.2949 m 170.42903 28.2949 m 170.42903 29.86055 169.15984 31.12975 167.5942 31.12975 c 166.02853 31.12975 164.75934 29.86055 164.75934 28.2949 c 164.75934 26.72925 166.02853 25.46005 167.5942 25.46005 c 169.15984 25.46005 170.42903 26.72925 170.42903 28.2949 c h 167.5942 28.2949 m B Q q 0.34 g 0.99628 w 0 G 0 g 0.34 g 201.82524 68.37561 m 204.6601 68.37561 m 204.6601 69.94125 203.3909 71.21045 201.82524 71.21045 c 200.2596 71.21045 198.99039 69.94125 198.99039 68.37561 c 198.99039 66.80995 200.2596 65.54076 201.82524 65.54076 c 203.3909 65.54076 204.6601 66.80995 204.6601 68.37561 c h 201.82524 68.37561 m B Q Q n Q 0 g 0 G0 g 0 G0 g 0 G0 g 0 G0 g 0 G1 0 0 1 -324 -309.987 cmBT/F15 11.9552 Tf 168.492 215.161 Td [(Figure6.2:Formingtheauxiliaryconvexgeometricgraph. Let D beanauxiliarydirectedgraphwithvertexset V D = f x 1 ;y 1 ;:::; x t ;y t g suchthat x i ;y i ; x j ;y j 2 E D ifandonlyif x i y j isan edgein G seeaandbinFigure6.2.Aseachvertex v in G hasatleast G )]TJ/F15 11.9552 Tf 12.908 0 Td [( n )-302(j X j)-302(j Y j )]TJ/F18 7.9701 Tf 6.675 -4.976 Td [(2 5 + n )]TJ/F15 11.9552 Tf 12.908 0 Td [( n )]TJ/F15 11.9552 Tf 11.955 0 Td [(2 t neighborsin X [ Y ,and n 5 2 t 70

PAGE 81

wehavethat + D 2 5 + n )]TJ/F15 11.9552 Tf 11.955 0 Td [( n )]TJ/F15 11.9552 Tf 11.956 0 Td [(2 t =2 t )]TJ/F26 11.9552 Tf 11.955 16.857 Td [( 3 5 )]TJ/F20 11.9552 Tf 11.955 0 Td [(" n 2 t )]TJ/F26 11.9552 Tf 11.955 16.857 Td [( 3 2 )]TJ/F20 11.9552 Tf 11.955 0 Td [(" t = 1 2 + t: .2 Thus e D )]TJ/F18 7.9701 Tf 6.675 -4.977 Td [(1 2 + t 2 andconsequentlythenumberof2-cyclesin D isatleast "t 2 Finally,let)-566(beaconvexgeometricgraphwith V \051= V D suchthat f x i ;y i ; x j ;y j g2 E \051ifandonlyif f x i ;y i ; x j ;y j g inducesa2-cyclein D .By .2, e \051 "t 2 ,soTheorem6.9impliesthat)-313(containsatleast "t pairwisedisjoint edges.These "t 2 5 "n k pairwisedisjointedgescorrespondtonon-overlapping pairsofconsecutivechordson H asinpartaofFigure6.2,whichallowustosplit H intoa2-factorwith k cycles,completingtheproof 71

PAGE 82

7.FutureWork InthischapterIwilltalkaboutmyplansforfuturework.Theseplansinclude short-rangeextensionsofresultsdiscussedinSection7.1,longer-termextensionsthat aremotivatedbytheresultsinSection7.2,andfascinatingproblemsthatIwould liketobeginthinkingaboutinSection7.3. 7.1DirectExtensions InTheorem3.4,weshowedthatanypairofforbiddensubgraphsthatimplies a4-connectedgraphispancyclicmustincludeeither K 1 ; 3 or K 1 ; 4 .InTheorem3.5, wethencharacterizedallpairsofforbiddensubgraphsinvolving K 1 ; 3 thatimplya 4-connectedgraphispancyclic.TheremainderofChapter3,andallofChapters4 and5relatedto4-connected K 1 ; 3 -freegraphs.Thisleavesopenthefollowingproblem. Problem7.1. Characterizethefamilyofgraphs H suchthatall4-connected, K 1 ; 4 free, H -freegraphsarepancyclic. NotethatTheorem3.4indicatesthateverygraph H in H mustbeaninduced subgraphofoneof P 9 L ,oroneofthegeneralizednets N i;j;k with i + j + k =6. Thus,wehaveaverytightboundsonwhat H couldpossiblybe.Ontheotherhand,I suspectthat H isempty.Toshowthis,weneedonlytonda4-connected, K 1 ; 4 -free, Y -freegraph G foreach Y 2f P 9 ; L ;N i;j;k g thatisnotpancyclic.Notethat,since foreachofthesegraphs Y ,every4-connected f K 1 ; 3 ;Y g -freegraphispancyclic, G musthaveaninducedcopyof K 1 ; 3 .Thustakingthelinegraphofsomegraph,a techniqueoft-usedintheproofofTheorem3.4,cannotbeusedtondsuchagraph andanotherconstructiontechniquemustbefound. InChapter6,webuiltanauxiliaryconvexgeometricgraph)-398(fromagraph G andusednon-crossingchordsin)-398(tonda2-factorwith k cyclesin G .However, thistechniquegaveusnocontroloverwhichverticesappearineachcycle.Onenice extensiontothis,wouldbetondawaytoforceeachcycletocontainaspecic vertexleadingtothenextproblem. 72

PAGE 83

Problem7.2. Determinethefunction f k;n suchthatthefollowingholds. If G isagraphon n verticeswithminimumdegreeatleast G f k;n ,then anyset S V G suchthat j S j = k containsa2-factorwith k cyclesandeachvertex in S appearsinadistinctcycle. In[17],DongndssharpOre-typedegreeconditionstoguaranteethatagraph hasa2-factorwith k cycleseachofwhichpassthroughaspeciedvertex.Moreover, hisresultguaranteesthatallbutoneofthecycleshaslengthatmost4.In[14],Chiba, Egawa,andYoshimotorenethisresulttondOre-typedegreeconditionswhereall butonecycleisatriangle.TheseOre-typeconditionsaremetiftheminimumdegree of G isatleast n + k )]TJ/F18 7.9701 Tf 6.586 0 Td [(1 2 TherearetwobarrierstoapplyingthesameapproachweusedtoproveTheorem6.6toProblem7.2.Therstisthatweneedtogaingreatercontrolofthe locationofanysetof k verticesalongahamiltoncycleofahamiltoniangraph.The secondisthatweneedtogainbettercontroloverwhichnon-crossingchordsappear inaconvexgeometricgraph. Agreatdealofworkhasgoneintodeterminingdegreeconditionsthatguarantee agraphhasahamiltoniancyclewithasetofverticesplacedalongthecycleinorder withspecieddistancebetweenthemseeforinstance[25],[27],and[46].However, noneoftheseassumeapriorithatthegraph G ishamiltonian. 7.2LocalChvatal-Erd}os Itisworthnotingthatthepropertyisclaw-free"isalocalpropertyinthesense thatitcanbecheckedbyexaminingeachvertexanditsneighborhoodindividually. Thusthepropertycanbecheckedinpolynomialtime.Similartothisistheproperty locallyconnected ;agraphissaidtobelocallyconnectediftheneighborhoodofevery vertexinducesaconnectedgraph.OberlyandSumnershowedthefollowing[54]. Theorem7.3. Everyconnected,locallyconnected,claw-freegraphoforder n 3 is hamiltonian. 73

PAGE 84

Asahamiltoniancycleisa2-factorwithexactlyonecomponent,ifwecould forcethe2-factortohaveonlyonecomponent,thenTheorem7.5wouldverifyConjecture7.4. Saito[63]pointedoutthatagraphisclaw-freeifandonlyif N [ v ] 2forevery vertex v .Also,agraphislocallyconnectedifandonlyif N [ v ] 2foreveryvertex v .ThustheconditioninTheorem7.3canbere-statedas N [ v ] 2 N [ v ]for everyvertex v .Hedenedthe localChvatal-Erd}os conditiontobetheconditionthat N [ v ] N [ v ]foreveryvertex v inagraph.Thusaclaw-free,locallyconnected graphsatisesthelocalChvatal-Erd}oscondition.Fromthis,heconjecturedthe following. Conjecture7.4. Everyconnectedgraphoforder n 3 satisfyingthelocalChvatalErd}osconditionishamiltonian. InsupportofConjecture7.4,Chenetal.[13]showedthefollowingconcerningthe localChvatal-Erd}osconditionand2-factors. Theorem7.5. Everyconnectedgraphoforder n 3 satisfyingthelocalChvatalErd}osconditionhasa2-factor. IwouldliketoapproachConjecture7.4byinvestigatingifRyjacek'sclosurecan beextendedtothelocalChvatal-Erd}osconditioninthefollowingway. Denition7.6. LettheChvatal-Erd}osclosureof G ,denoted cl CE G ,bethegraph formedbyiterativelyaddingallmissingedgestotheneighborhoodofavertex v if N [ v ] N [ v ] ,but N [ v ] isnotcomplete. Iwouldliketoinvestigatewhetherornottherearenon-hamiltoniangraphs G suchthat cl CE G ishamiltonian. 74

PAGE 85

7.3OtherDirections Finally,long-termIwouldliketostartusingmorecomputationaltechniquesinmy research.Here,Iwilltalkabouttwowaystodothis.Therstisthroughexhaustive search,andthesecondisbyusingextremalstructureswithinagraph. IndiscussingProblem7.1,Imentionedthefactthatweneedonlynda4connected, K 1 ; 4 -free, Y -freegraph G foreach Y 2f P 9 ; L ;N i;j;k g thatisnotpancyclicinordertoshowthatthepairsofforbiddensubgraphslistedinTheorem3.5in factcharacterizeallpairsofforbiddensubgraphsthatimplya4-connectedgraphis pancyclic.Onepossibleapproachtothisistosimplyexhaustivelylisteverypossible graphonatmost k verticesandchecktoseeifeachofthesegraphsis4-connected, and f K 1 ; 4 ;H g -freefortheappropriategraphs H .Thereare,ofcourse,severalproblemswiththisincludingthefactthatitisdiculttoruleoutisomorphicgraphsso thesearchspaceisunnecessarilylarge,andforanyreasonablevalueof k ,evenifwe ruleoutisomorphicgraphsthesearchspaceisfartoolargetosonaivelysearch. Thus,inordertoeectivelyusetheexhaustivesearchtechnique,werstmust developanecientmethodologyforatleastoneofthefollowing: Produceallnon-isomorphic4-connectedgraphs. Produceallnon-isomorphic K 1 ; 4 -freegraphs. Findsomeotherwaytolimitthesearchspace. Onepossibletechniquetolimitthesearchspacewouldbetondaconstruction thatproducesafamily F of4-connected, K 1 ; 4 -freegraphsandthenprove,possibly throughaclosureoperation,thatifthereisa4-connected, K 1 ; 4 -freegraphthatisnot pancyclic,thenthereisanon-pancyclicgraphinthefamily F 75

PAGE 86

REFERENCES [1]J.AkiyamaandM.Kano. Factorsandfactorizationsofgraphs ,volume2031of LectureNotesinMathematics .Springer,Heidelberg,2011.Prooftechniquesin factortheory. [2]D.Amar,E.Flandrin,I.Fournier,andA.Germa.PancyclisminHamiltonian graphs. DiscreteMath. ,89:111{131,1991. [3]P.M.Bedrossian. Forbiddensubgraphandminimumdegreeconditionsforhamiltonicity .ProQuestLLC,AnnArbor,MI,1991.ThesisPh.D.{MemphisState University. [4]J.A.Bondy.PancyclicgraphsI. J.CombinatorialTheorySer.B ,11:80{84, 1971. [5]J.A.BondyandV.Chvatal.Amethodingraphtheory. DiscreteMath. ,15:111{ 135,1976. [6]S.Brandt,G.Chen,R.Faudree,R.J.Gould,andL.Lesniak.Degreeconditions for2-factors. J.GraphTheory ,24:165{173,1997. [7]S.Brandt,O.Favaron,andZ.Ryjacek.ClosureandstableHamiltonianpropertiesinclaw-freegraphs. J.GraphTheory ,34:30{41,2000. [8]H.BroersmaandD.Paulusma.Computingsharp2-factorsinclaw-freegraphs. J.DiscreteAlgorithms ,8:321{329,2010. [9]H.Broersma,D.Paulusma,andK.Yoshimoto.Sharpupperboundsontheminimumnumberofcomponentsof2-factorsinclaw-freegraphs. GraphsCombin. 25:427{460,2009. [10]H.Broersma,Z.Ryjacek,andI.Schiermeyer.Closureconcepts:asurvey. Graphs Combin. ,16:17{48,2000. [11]H.BroersmaandH.J.Veldman.Restrictionsoninducedsubgraphsensuring Hamiltonicityorpancyclicityof K 1 ; 3 -freegraphs.In Contemporarymethodsin graphtheory ,pages181{194.BibliographischesInst.,Mannheim,1990. [12]J.S.Carraher,M.J.Ferrara,T.Morris,andM.Santana.Characterizingforbiddensubgraphsimplyingpancyclicityin4-connectedclaw-freegraphs.InPreparation. [13]G.Chen,A.Saito,andS.Shan.TheExistenceofa2-FactorinaGraphSatisfyingtheLocalChvatal{ErdosCondition. SIAMJ.DiscreteMath. ,27:1788{1799, 2013. 76

PAGE 87

[14]S.Chiba,Y.Egawa,andK.Yoshimoto.A2-factorinwhicheachcyclecontains avertexinaspeciedstableset. Australas.J.Combin. ,46:203{210,2010. [15]V.ChvatalandP.Erd}os.AnoteonHamiltoniancircuits. DiscreteMath. 2:111{113,1972. [16]G.A.Dirac.Sometheoremsonabstractgraphs. Proc.LondonMath.Soc. 2:69{81,1952. [17]J.Dong.Smallcyclesand2-factorpassingthroughanygivenverticesingraphs. J.Appl.Math.Comput. ,34:485{493,2010. [18]D.Duus,M.S.Jacobson,andR.J.Gould.Forbiddensubgraphsandthe Hamiltoniantheme.In ThetheoryandapplicationsofgraphsKalamazoo,Mich., 1980 ,pages297{316.Wiley,NewYork,1981. [19]Y.EgawaandK.Ota.Regularfactorsin K 1 ;n -freegraphs. J.GraphTheory 15:337{344,1991. [20]P.Erd}os.Someproblemsingraphtheory.In HypergraphSeminarProc.First WorkingSem.,OhioStateUniv.,Columbus,Ohio,1972;dedicatedtoArnold Ross ,pages187{190.LectureNotesinMath.,Vol.411.Springer,Berlin,1974. [21]J.R.Faudree,R.J.Faudree,andZ.Ryjacek.Forbiddensubgraphsthatimply 2-factors. DiscreteMath. ,308:1571{1582,2008. [22]R.Faudree,O.Favaron,E.Flandrin,H.Li,andZ.Liu.On2-factorsinclaw-free graphs. DiscreteMath. ,206:131{137,1999.Combinatoricsandnumbertheory Tiruchirappalli,1996. [23]R.Faudree,R.Gould,Z.Ryjacek,andI.Schiermeyer.Forbiddensubgraphs andpancyclicity.In ProceedingsoftheTwenty-sixthSoutheasternInternational ConferenceonCombinatorics,GraphTheoryandComputingBocaRaton,FL, 1995 ,volume109,pages13{32,1995. [24]R.J.FaudreeandR.J.Gould.CharacterizingforbiddenpairsforHamiltonian properties. DiscreteMath. ,173:45{60,1997. [25]R.J.FaudreeandR.J.Gould.PreciselocationofverticesonHamiltoniancycles. DiscreteMath. ,313:2772{2777,2013. [26]R.J.Faudree,R.J.Gould,M.S.Jacobson,L.Lesniak,andA.Saito.Anoteon 2-factorswithtwocomponents. DiscreteMath. ,300:218{224,2005. [27]R.J.Faudree,R.J.Gould,M.S.Jacobson,andC.Magnant.Distributing verticesonHamiltoniancycles. J.GraphTheory ,69:28{45,2012. [28]S.Felsner. Geometricgraphsandarrangements .AdvancedLecturesinMathematics.Friedr.Vieweg&Sohn,Wiesbaden,2004.Somechaptersfromcombinatorialgeometry. 77

PAGE 88

[29]M.Ferrara,S.Gehrke,R.Gould,C.Magnant,andJ.Powell.Pancyclicityof 4-connected f claw,generalizedbull g -freegraphs. DiscreteMath. ,313:460{467, 2013. [30]M.Ferrara,T.Morris,andP.Wenger.Pancyclicityof4-connected,claw-free, P 10 -freegraphs. J.GraphTheory ,71:435{447,2012. [31]E.Flandrin,H.Li,A.Marczyk,I.Schiermeyer,andM.Wozniak.Chvatal-Erd}os conditionandpancyclism. Discuss.Math.GraphTheory ,26:335{342,2006. [32]M.R.GareyandD.S.Johnson. Computersandintractability .W.H.Freeman andCo.,SanFrancisco,Calif.,1979.AguidetothetheoryofNP-completeness, ASeriesofBooksintheMathematicalSciences. [33]M.R.Garey,D.S.Johnson,andL.Stockmeyer.SomesimpliedNP-complete graphproblems. Theoret.Comput.Sci. ,1:237{267,1976. [34]C.GodsilandG.Royle. Algebraicgraphtheory ,volume207of GraduateTexts inMathematics .Springer-Verlag,NewYork,2001. [35]S.GoodmanandS.Hedetniemi.SucientconditionsforagraphtobeHamiltonian. J.CombinatorialTheorySer.B ,16:175{180,1974. [36]R.J.Gould.UpdatingtheHamiltonianproblem|asurvey. J.GraphTheory 15:121{157,1991. [37]R.J.Gould.AdvancesontheHamiltonianproblem|asurvey. GraphsCombin. 19:7{52,2003. [38]R.J.Gould.Alookatcyclescontainingspeciedelementsofagraph. Discrete Math. ,309:6299{6311,2009. [39]R.J.Gould.RecentadvancesontheHamiltonianproblem:SurveyIII. Graphs Combin. ,30:1{46,2014. [40]R.J.GouldandM.S.Jacobson.ForbiddensubgraphsandHamiltonianpropertiesofgraphs. DiscreteMath. ,42:189{196,1982. [41]R.J.Gould,T.Luczak,andF.Pfender.Pancyclicityof3-connectedgraphs: pairsofforbiddensubgraphs. J.GraphTheory ,47:183{202,2004. [42]E.GyoriandH.Li.2-factorsinhamiltoniangraphs.InPreparation. [43]J.HopcroftandR.Tarjan.Algorithm447:Ecientalgorithmsforgraphmanipulation. Commun.ACM ,16:372{378,June1973. [44]B.Jackson.Hamiltoncyclesin7-connectedlinegraphs.1989. [45]T.KaiserandP.Vrana.Hamiltoncyclesin5-connectedlinegraphs. European J.Combin. ,33:924{947,2012. 78

PAGE 89

[46]A.KanekoandK.Yoshimoto.A2-factorwithtwocomponentsofagraph satisfyingtheChvatal-Erd}oscondition. J.GraphTheory ,43:269{279,2003. [47]Y.S.Kupitz.Onpairsofdisjointsegmentsinconvexpositionintheplane. In ConvexityandgraphtheoryJerusalem,1981 ,volume87of North-Holland Math.Stud. ,pages203{208.North-Holland,Amsterdam,1984. [48]M.-C.Li,D.G.Corneil,andE.Mendelsohn.PancyclicityandNP-completeness inplanargraphs. DiscreteAppl.Math. ,98:219{225,2000. [49]A.Lubotzky,R.Phillips,andP.Sarnak.Ramanujangraphs. Combinatorica 8:261{277,1988. [50]T.LuczakandF.Pfender.Claw-free3-connected P 11 -freegraphsareHamiltonian. J.GraphTheory ,47:111{121,2004. [51]W.Mader.Minimale n -fachkantenzusammenhangendeGraphen. Math.Ann. 191:21{28,1971. [52]M.M.MatthewsandD.P.Sumner.Hamiltonianresultsin K 1 ; 3 -freegraphs. J. GraphTheory ,8:139{146,1984. [53]C.S.J.A.Nash-Williams.Edge-disjointHamiltoniancircuitsingraphswith verticesoflargevalency.In StudiesinPureMathematicsPresentedtoRichard Rado ,pages157{183.AcademicPress,London,1971. [54]D.J.OberlyandD.P.Sumner.Everyconnected,locallyconnectednontrivial graphwithnoinducedclawisHamiltonian. J.GraphTheory ,3:351{356,1979. [55]O.Ore.NoteonHamiltoncircuits. Amer.Math.Monthly ,67:55,1960. [56]F.Pfender.2-factorsinHamiltoniangraphs. ArsCombin. ,72:287{293,2004. [57]M.D.Plummer.Graphfactorsandfactorization:1985{2003:asurvey. Discrete Math. ,307:791{821,2007. [58]L.Posa.AtheoremconcerningHamiltonlines. MagyarTud.Akad.Mat.Kutato Int.Kozl. ,7:225{226,1962. [59]Z.Ryjacek.Onaclosureconceptinclaw-freegraphs. J.Combin.TheorySer. B ,70:217{224,1997. [60]Z.Ryjacek,A.Saito,andR.H.Schelp.Claw-freegraphswithcompleteclosure. DiscreteMath. ,236:325{338,2001.GraphtheoryKazimierzDolny,1997. [61]Z.Ryjacek,Z.Skupien,andP.Vrana.Oncyclelengthsinclaw-freegraphswith completeclosure. DiscreteMath. ,310:570{574,2010. [62]Z.RyjacekandP.Vrana.LinegraphsofmultigraphsandHamiltonconnectednessofclaw-freegraphs. J.GraphTheory ,66:152{173,2011. 79

PAGE 90

[63]A.Saito.Chvatal-Erd}ostheorem:oldtheoremwithnewaspects.In Computationalgeometryandgraphtheory ,volume4535of LectureNotesinComput.Sci. pages191{200.Springer,Berlin,2008. [64]G.N.Sarkozy.On2-factorswith k components. DiscreteMath. ,308:1962{1972, 2008. [65]F.B.Shepherd.Hamiltonicityinclaw-freegraphs. J.Combin.TheorySer.B 53:173{194,1991. [66]C.Thomassen.Reectionsongraphtheory. J.GraphTheory ,10:309{324,1986. [67]D.West.Personalcommunication. [68]K.Yoshimoto.Onthenumberofcomponentsin2-factorsofclaw-freegraphs. DiscreteMath. ,307:2808{2819,2007. 80