图和有向图的测地数

• 作者: 吕长虹
• 来源期刊: 中国科学A辑
• 学科: 数学
• 关键词: 凸集 有向图 距离 测地线 测地数
• 年，卷（期）: 2007,（5）
• 页码范围: 579-586
• 页数: 8页
• 分类号: O1
• 字数: 8016字
• 语种: 中文
• DOI: 10.3321/j.issn:1006-9232.2007.05.008

摘要

图G内的任意两点u和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的相关结论.