赋权图中最重的最长v-路与赋权周长

THE HEAVIEST LONGEST v-PATHS AND WEIGHTED CIREUMFERENCES OF WEIGHTED GRAPHS

对 2 -连通非Hamilton赋权图G ,本文证明 :若P(u ,v)是G中最重的最长路 ,则G的赋权周长cw(G)≥dw(u) +dw(v) ;假设G满足文中描述的额外条件C1 、C2 ,则max{dw(x) ,dw(y) |d(x ,y) =2 }≥m/ 2时 ,对每个顶点v ,G含最重最长υ -路P(u ,v)使dw(u)≥m/ 2 ,而dw(x) +dw( y) +dw(z)≥m(当d(x ,y ,z) =2 )时 ,cw(G)≥ 2m/ 3.改进了非赋权图的周长及赋权图的赋权周长的若干已有结果 .

It is proved that for a 2-connected nonhamiltonian weighted graph G,the weighted circumference c w(G) is at least d w(u)+d w(v) if P(u,v) is a heaviest longest path in G.Suppose G Satisfy two extra conditions C 1 and C 2 mentioned in the paper,then G contains a heaviest longest v-path P(u,v) such that d w(u)≥m/2 for any vertex v if we have max {d w(x),d w(y)|d(x,y)=2}≥m/2,and c w(G)≥2m/3 if d w(x)+d w(y)+d w(z)≥m for any three vertices x,y and z with d(x,y,z)=2.Those results improve several known results on circumferences of (unweighted) graphs or weighted circumferenes of weighted ones.