|
|||||
|
|
| 图和有向图的测地数 | |
| 作者姓名： | 吕长虹 |
| 作者单位： | 华东师范大学数学系, 华东师范大学计算机理论研究所, 上海 200062 |
| 基金项目： | 国家自然科学基金;上海市科委资助项目 |
| 摘 要： | 图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 的相关结论. |
| 关 键 词： | 有向图 距离 测地线 测地数 凸集 |
| 收稿时间： | 2005-05-29 |
| 修稿时间： | 2005-05-29 |
| 本文献已被 CNKI 万方数据 等数据库收录！ | |
| 点击此处可从《中国科学A辑》浏览原始摘要信息 | |
| 点击此处可从《中国科学A辑》下载免费的PDF全文 | |