论文部分内容阅读
本文主要介绍图和有向图的测地数的研究进展和在这方面所做的工作,主要工作包括以下三个部分:
(1)确定测地数为n-1,n-2的图G的结构;
(2)考虑测地数为5的图G,证明该类图对于吕长虹在文献[4]中提出的猜想成立;
(3)讨论了T×K3的测地数。
介绍了无向图的测地数。在[10]中,GaryChartrand,FrankHarary和PingZhang证明了g(G)=n当且仅当G是完全图Kn,本文继续他们的工作,确定了(1)测地数g(G)=n-1当且仅当G≌H∨K1,其中H=Ks1∪Ks2∪…∪Ksk(k≥2,si≥1i=1,2,…,k),(2)测地数g(G)=n-2当且仅当G有如下性质:Ⅰ.存在两个顶点x,y使得G-{x,y}≌Ks1∪Ks2∪…∪Ksk(k≥2,si≥1i=1,2,…,k)Ⅱ.当图的直径diam(G)=2时,对Gi可作如下划分:Gi=Xi∪Ai∪Yi,其中Xi={v|v∈{V(Gi)∩N(x),v(∈)N(y)};Yi={v|v∈{V(Gi)∩N(y),v(∈)N(x)};Ai={v|v∈V(Gi),v∈N(x)∩N(y)},若Xi≠(0),则|Yi∪Ai|≤2;若Yi≠(0),则|Xi∪Ai|≤2,并且满足不同时存在两个以上的连通分支Gi,Gj使得Xi,Yj,Xj∩Aj均不为空集,或者Yi,Xj,Yj∩Aj均不为空集。Ⅲ.当diam(G)=2,x,y不相邻时,G中有一点与x,y都相邻且至多有两点与x,y都相邻。Ⅳ.当diam(G)=3时,x,y必相邻,在G-{x,y}中至少存在两个连通分支,它们的顶点分别都是x,y的邻居;对其余连通分支,若N(x)∩V(Gi)≠(0),则V(Gi)(∈)N(x),对y该性质同样成立。
讨论了有向图的测地数。在[4]中,吕长虹提出了一个关于图的测地数的猜想:对于图G,g(G)≤g+(G)。同时他还证明了所有g(G)≤4的图G,对于上述猜想都成立。本文在此基础上,考虑所有g(G)=5的图G,通过对图最小测地集的分析,证明该类图对于上述猜想也成立。
研究了图的笛卡儿积G×Kn的测地数,得出了下列结论:对于一棵有l个叶子的树T,g(T×Km)=max{l,m}。