图和有向图的测地数  

作　　者：吕长虹[1] 

机构地区：[1]华东师范大学数学系,华东师范大学计算机理论研究所,上海200062

出　　处：《中国科学（A辑）》2007年第5期579-586,共8页Science in China(Series A)

基　　金：国家自然科学基金(批准号:10301010;60673048);上海市科委(批准号:04JC14031)资助项目

摘　　要：图G内的任意两点y和v,u-v测地线是指u和v之间的最短路．I(u,v)表示位于u-v测地线上所有点的集合,对于子集S (?) V(G),I(S)表示所有I(u,v)的并,这里u,v∈S．图G的测地数g(G)是使得I(S)=V(G)的点集S的最小基数．对于有向图D,类似地可定义g(D)．图G的测地谱是G的所有定向图的测地数的集合,记为S(G)．G的下测地数g-(G)=minS(G),上测地数g+(G)=maxS(G)．文中主要研究了连通图G的g(G), g-(G)和g+(G)之间的关系．同时,还给出g(G)和g(G×K2)相等的充分必要条件,从而推广了Chartrand,Harary和Zhang的相关结论．

关 键 词：凸集 有向图 距离 测地线 测地数 

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