论文部分内容阅读
图G的距离和是G的所有顶点对之间距离的和,记为σ(G),也被称为“Wiener指数”.图G的平均距离是G的所有点对(若G为有向图,则为有序点对)之间的距离和的平均值,记为μ(G).图G的任意两点的度与它们之间距离的乘积的和,记为Gut.图G的定向是对G的每条边指定一个方向,这样由G得到的有向图D叫做G的定向.如果G的定向D中任意两点之间可以相互到达,则称D为G的强定向. 本文分为四章,主要内容如下: 第一章的第一部分介绍了图的一些基本概念和术语.第二部分给出Wiener指数的研究进展以及一些重要结果. 第二章主要讨论了强连通简单欧拉图的wiener指数的上界和下界,证明了: 定理D是最小外度为δ(2≤δ≤n/2)的n阶强连通简单欧拉图,则σ(D)≤n(2n+δ-2)2/8δ 定理D是一个最小外度为δ(2≤δ≤n/2)的n阶强连通简单欧拉图,如果D没有2圈,则σ(D)≥ n(n-1)-2n(2δ-1)2/2δ+1 第三章主要讨论了图的Gut指数,并给出了一些简单的结果,证明了: 定理G是一个n阶简单连通图,则Gut(G)≤1/3△2n(n-1)(n+1) 定理Ka,b是一个部集顶点数分别为a,b的完全二部图,则Gut(Ka,b)=4a2b2-ab2-a2b 第四章主要讨论了树的独立数与其补图的独立数的关系,证明了: 定理若T为一棵n(≥2)阶树,则△+2≤α(T)+α(Tc)≤{ n-(n-1/△)+2 r(n-1/△)=0n-([)n-1/△」+1 r(n-1/△)≠0 其中r(n-1/△)表示n-1除以△后所得的余数. 定理设T为一棵n(≥4)阶树,α(T)=n-2当且仅当T具有给定的图2、图3(见正文)的结构.