单圈图与双圈图的harary指标.doc

具有最值指数的单圈图和双圈图徐珂想、:设是一个简单连通图,则图的指数定义为图中所有点对反距离和的一半。在这篇文章中,我们主要讨论具有指数的单圈图和双圈图。关键词:单圈图,双圈图,指数,直径1基本概念设表示图的指数,它是1993年由和等各自独立引入的拓扑指数。以纪念七十岁生日而命名。图的指数定义如下:,其中表示图的任两点,的距离(连接任两点,最短路的边数)。文献中讨论了指数的数学理论和应用。指数是基于距离的基础提出的一种拓扑指数。它是1947年由等最早引入的拓扑指数,定义如下:=即所有点对距离之和的一半。文献中讨论了指数的数学理论和应用。设表示图中距离为的点对。那么(1)。设图为不连通图,则不同部分两点间距离为无穷,反距离定义为0。不连通图的指数定义如下:,其中是图的所有部分。这篇文章介绍的是有限、简单、连通图。设图的顶点集,边集为。设点,表示此点的度数(简写)即与此点相连的点数。特别表示图的最大度。度数为1的点为悬挂点。与悬挂点相邻的边为悬挂边。设是顶点集的子集,设G-W是图的子图。类似,设是边集的子集,G-是图的子图。如果=,则子图G-W,G-分别简写为G-,G-。图中不相连的两点,,G+表示在此两点添加一条边。如果满足,称此连通图为单圈图。如果满足+1,称此连通图为双圈图。表示n个顶点的路,圈,星图。其它没定义的理论参见文献。设分别表示连通n个顶点的单圈图和双圈图。一个图的最大度为4称为分子图,模型参见文献。Gutman最先提出了具有最值指数的树图。更多理论和应用参见文献。特别,周和Trinajstic[14],周和Cai[30]给出了精彩指数最值。这篇文章主要讨论具有最值指数的单圈图和双圈图。2主要引理这部分我们主要罗列和证明了一些引理,同时一些必备知识应用到一些列证明。首先,设连通图,任意,定义。为了方便把写为。函数是严格增函数,当时。,是图的悬挂点,其中,那么。证明:根据指数和定义,===,是图的不相连得两点,并且,那么(1)(2),其中,那么等式成立的充分必要条件是是图的悬挂点。设(见图1(a))是n个顶点的星树,它是m条路代替星图的m条边获的,其中。如果中的个数,记为。n个顶点并且有k叶子为扫帚图记为 (见图1(b))与最大度相连得叶子称为单元叶。设其中 是图中单元叶中添加某些边得到。如果是的一个悬挂点,此点与有最大度k的点距离为n-k,那么。 设n个顶点的连通图,直径,对任意点v,,(2) 式成立的充分必要条件是,点v是此图中与最大度点距离为k-1的点。证明:假定是一条路,其中点与相连,。(3)其中。如果k=d由(3)式得(2)式成立。另外,当k>d时,<,即< 即=<,即<,当d<k<n时。