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

The Degree Sum and Traceable Property of n-Extendable Graph

作　　者：黄月梅[1] 

机构地区：[1]内蒙古师范大学数学科学学院,内蒙古呼和浩特010022

出　　处：《内蒙古师范大学学报（自然科学汉文版）》2004年第2期128-130,共3页Journal of Inner Mongolia Normal University(Natural Science Edition)

摘　　要：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.A graph G of order at least 2n+2 is said to be n-extendable if it has a perfect matching and every set of n independent edges extends to a perfect matching in G.Let G be a connected n-extendable graph of order p,(SV(G)),we define σ_3(S,G)=min {∑3i=1d(x_i):{x_1,x_2,x_3} S and an independent set of G}, p(S,G)=max {|V(P)∩S|:P is a path of G}, c(S,G)=max {|V(C)∩S|:C is a cycle of G}. A subset S is said to be traceable in G,if p(S,G)=|S| .A cycle C is said to be S-maximum cycle,if |V(C)∩S|=(c(S,G)).In this paper we will prove that if σ_3(S,G)≥32(p-2n)-4 then S is traceable in G or c(S,G)≥(p(S,G)-1).

关 键 词：n-扩张图 度和 可迹性 圈 路 

分 类 号：O157.5[理学—数学]