图和有向图的测地数

作     者：吕长虹 

作者机构：华东师范大学数学系华东师范大学计算机理论研究所上海200062 

出 版 物：《中国科学（A辑）》 (Science in China(Series A))

年 卷 期：2007年第37卷第5期

页      面：579-586页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：国家自然科学基金(批准号: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的相关结论．