n -扩张图的度和与可迹性(英文)

摘要

AgraphGoforderatleast 2n +2issaidtoben extendableifithasaperfectmatchingandeverysetofnindependentedgesextendstoaperfectmatchinginG .LetGbeaconnectedn extendablegraphoforder p ,S V(G) ,wedefineσ3 (S ,G) =min { ∑3i=1d(xi) :{x1,x2 ,x3 } SandanindependentsetofG} ,p(S ,G) =max { |V(P)∩S|:PisapathofG} ,　　c(S ,G) =max { |V(C)∩S|:CisacycleofG} .AsubsetSissaidtobetraceableinG ,ifp(S ,G) =|S|.AcycleCissaidtobeS maximumcycle ,if |V(C)∩S|=c(S ,G) .Inthispaperwewillprovethatifσ3 (S ,G)≥ 32 (p - 2n) - 4thenSistraceableinGorc(S ,G)≥p(S ,G) - 1.研究了n -扩张图的度和与可迹性 ,利用度和证明了对于n -扩张图G且S V(G) ,如果σ3 (S ,G)≥ 32 (p - 2n) - 4 ,则S在G中可迹 ,或c(S ,G)≥p(S ,G) - 1.