论文部分内容阅读
连通图G中的任意两点u和v,一条u-v测地线是指u,v两点间的最短路。令Lu,v表示位于u-v测地线上所有点的集合。对于子集S,令I(S)=Uu,v∈I(u,v),如果I(S)=V(G),则我们称S是G的测地集。把图G测地集的最小基数叫做G的测地数。同样我们可以相对应的定义有向图D的相关概念.对图G的所有边给定一个方向后的图称为图G的定向图,我们称S(G)={g(D):D是图G的定向图}为图G测地数的谱。g+(G)=maxS(G)为图G的上测地数。本文讨论了无向图以及有向图的测地数,主要内容如下:
在第一章中,我们简单介绍了图测地集研究的背景与已有的一些结果。
在第二章中,我们研究上测地数下界的一个猜想:如果图G是一个直径为d最小度为δ的非平凡的连通图,则有g+(G)≥d+δ。证明了这个猜想对无三圈图,△(G)≤3的图以及单位区间图是正确的。
在第三章中,我们先给出了二部图与完全图笛卡尔积上测地数的下界。并且研究图上测地数与测地数大小关系的一个猜想:对所有的图都有g+(G)≥g(G)。证明了树与完全图的笛卡尔积同时满足g+(G)≥g(G)与g+(G)≥d+△。还讨论了树与完全图的笛卡尔积的测地数与d+△的关系。
在第四章,我们给出了块图的测地数,并且研究了块图上测地数的范围。