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

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

作　　者：高敬振[1] 姜学波[2] 

机构地区：[1]山东师范大学数学系,济南250014 [2]山东工会干部管理学院计算机科学系,济南250100

出　　处：《山东师范大学学报（自然科学版）》2002年第2期1-4,共4页Journal of Shandong Normal University(Natural Science)

基　　金：国家自然科学基金资助项目 ( 199710 5 3)

摘　　要：对 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.

关 键 词：赋权图 最长v-路 赋权周长 赋权度 最重最长v-路 2-连通非Hamilton图 

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