论文部分内容阅读
图的测地数是揭示图的结构特性的一个重要参数。图的测地数源于几何学、拓扑学和函数分析中的凸集理论，是凸集理论在图论中的应用和推广，也与图论中“路覆盖”和“路分解”等问题相关联。
本文主要介绍图和有向图的测地数的研究进展和本人在这方面所做的工作，主要的工作包括以下四个部分：(1)给出完全r-部图的测地数；(2)研究了Gu+Hv的测地数及其上测地数和下测地数；(3)研究了GuoHv的测地数及其上测地数和下测地数；(4)讨论了G×K3的测地数。
在第二章中，介绍了无向图的测地数，我们主要做了以下二方面的工作：●在文献[10]，GaryChartrand，FrankHarary和PingZhang给出了完全二部图的测地数，即：g(Kr,s)=min{r,s，4}(r,s≥2)，我们类似地给出完全r-部图的测地数，即：g(Kn1，n2，…，nr)=min{n1，4}，其中ni≥2，i=1，2，…，r且n1≤n2≤…≤nr.●在文献[4]，吕长虹考察了图的两种运算Gu+Hv和GuoHv，得出当u，v分别属于G和H最小测地集时，有g(Gu+Hv)=g(G)+g(H)-2和g(GuoHv)=g(G)+gH)-2。我们推广上面的结论，证明了对于u和v分别是G和H中的任意点，都有g(G)+g(H)-2≤g(Gu+Hv)≤g(G)+g(H)，g(G)+g(H)-2≤g(GuoHv)≤g(G)+g(H).
在第三章中，讨论了有向图的测地数，我们主要研究了Gu+Hv和GuoHv的上(下)测地数，证明了下列结果：
●设G和H是非平凡图，对于u∈V(G)，v∈V(H)，则g+(G)+g+(H)-2≤g+(Gu+Hv)≤g+(G)+g+(H)，g-(G)+g-(H)-2≤g-(Gu+Hv)≤g-(G)+g-(H)；g+(G)+g+(H)-2≤g+(GuoHv)≤g+(G)+g+(H)，g-(G)+g-(H)-2≤g-(GuoHv)≤g-(G)+g-(H).●设G和H是两个非平凡图，当u和v分别是G和H的悬挂点时，有g+(Gu+Hv)=g+(G)+g+(H)，g-(Gu+Hv)=g-(G)+g-(H)-2；g+(GuoHv)=g+(G)+g+(H)-1，g-(GuoHv)=g-(G)+g-(H)-2.
在第四章，我们研究了图的笛卡儿积G×K3的测地数，得出了下列结论：●设G是非平凡连通图，如果G包含某个最小测地集S，在S中存在一点x使得G中的任意点都位于x-w测地线上，其中w∈S，那么g(G)≤g(G×K3)≤g(G)+1.
●设G是阶数至少为3的连通图，那么g(G)=g(G×K3)当且仅当存在最小测地集S和基于S的测地族F使得S相对于F分成(S1，S2，S3).●设树Tn有l(≥3)个树叶，则g(Tn×K3)=g(Tn)=l.