复合图的乘权Harary指数（英文）

分子图的乘权Harary指数H_M(G),被定义为■,其中d_G(u)表示图G中顶点u的度,d_G(u,v)表示图G中顶点u和v之间的距离.本文主要研究4种图操作下得到的复合图的乘权Harary指数,以及在4种图操作下一些特殊复合图的乘权Harary指数的上下界.     

固定直径的树的Harary指数

图G的Harary指数定义为图中所有点对的反距离之和.给出了固定直径的树的Harary指数的第二大值,并刻画了对应的极图.     

两类粘合图的 Wiener与 Harary指数

连通图G的Wiener指数是指图G中所有点对的距离之和,Harary指数是指图G中所有点对的距离的倒数之和。本文主要研究了单圈图与双圈图的粘合图以及双圈图与双圈图的粘合图的Wiener指数的下界和Harary指数的上界的问题,并刻画了对应的极值图。     

连通图的Harary指数上界及其极图

图的Harary指数定义为图的所有顶点对的距离的倒数之和.刻画了在给定点数和直径的图类中,Harary指数达到最大的极图,并由此确定了Harary指数关于直径的一个上界.另外,在n阶连通图中,刻画了Harary指数达到第二大和第三大的图的结构.     

(p、q)图的最大直径的一点注记

F.Harary为了解答C.Berge在他1958年书中的一个问题,写了题为“图的最大连通度”一文。在文末,他附带讨论了(p、q)图的最小与最大直径的估计问题。其中比较有趣的是给出了连通的(p、q)图的最大直径的计算公式。这个计算公式是不对的。下面先重述一下Harary的“公式”,然后举一个简单例子坐实这个公式的不堪使用,最后把它改正为可以使用的形式。按Harary的记号,p是简单(无向)图G的顶点数,q是G的棱数,m=q-p+1是     

匹配数给定的一类拓扑指标的上界（英文）

当一个图的匹配数给定,求出了超Zagreb指标、Harary指标和Wiener指标的上界,并刻画出极图.     

具有k个悬挂点的n阶单圈图的Harary指数(英文)

连通图的Harry指数定义为所有顶点对的距离倒数和.本文对具有k个悬挂点的n阶单圈图的Harary指数进行了研究,并给出了此类图中具有极大Harary指数的图类.     

具有k个悬挂点的双圈图的Harary指数

双圈图是指顶点数等于边数减1的连通图,Harary指数是指图中所有顶点对的距离倒数之和.基于此,主要研究了具有k个悬挂点且两个圈只有一个交点的n阶双圈图有极大Harary指数的图类.     

给定悬挂点数图的 Harary指数的极图

图的Harary 指数定义为图中所有顶点对的距离的倒数之和。本文我们刻画了给定顶点数和悬挂点数的图类中,Harary 指数取到最大、第二大、第三大的极图,并由此确定了关于悬挂点数的Harary 指数上界。     

关于标定图重构的一条定理

一九二九年,S·R·Ulam提出一个猜想,认为图G的除点v_i外的所有点和与v_i不关联的所有边组成的子图G_i的总体可以给出足够多的关于G本身的信息.这就是图论中著名的重构问题,迄今仍未解决.对于不连通图、树和少数其它类型的图,这一猜想已被证实(Harary,1974).近年来,国内有人尝试从部分标定图出发去证明这一猜想.     

给定悬挂点数图的Harary指数的极图

图的Harary指数定义为图中所有顶点对的距离的倒数之和。本文我们刻画了给定顶点数和悬挂点数的图类中,Harary指数取到最大、第二大、第三大的极图,并由此确定了关于悬挂点数的Harary指数上界。     

直径稳定图和边直径稳定度

一个图 G 称为是一个(l,d)——稳定图(关于边的),如果对于 G 的边集 E(G)的任意一个子集 E,只要满足 E 中的边数≤l-1,都有图 V-E 的直径 d(V-E)≤d。(这里 l,d 都是正整数)。如果更有G 的直径 d(G)=d,则称 G 为 l 直径稳定图。一个图 G 的边直径稳定度(line-persistence)ρ_1(G)是为了要使得在 G 中去掉一些边后所得到的图 G′的直径 d(G′)>d(G)或者使 G′不连通所必须去掉的最少边数。(l,d)——稳定图和 l 直径稳定图的概念是首先由 J.Hartman 和 I.Rubin 于1956年在[1]中提出的。直径稳定度的概念是由 F.T.Boesch;F.Harary 和 J.A.Kabell 于1981年在[2]中首先提出的。本文对直径稳定图和边直径稳定度作了进一步的考察,得到了一些关于直径稳定图的结论,并初步讨论了直径稳定图和边直径稳定度之间的关系,最后,通过一个引理和一个推论给出了几个 l 直径稳定图族,从而解决了 Hartman 和 Rubin 在[1]中提出的两个问题,同时所给出的图族证明了 Boesch;Harary 和 Kabell 在[2]中所给出的一个关于边直径稳定度的“定理”是不正确的。(注:此“定理”有两种“等价”的叙述方法,本文所给出的图可作为这两种叙述的反例。)     

二正则图的和数

设S是自然数集N*的一个有限集.定义在S上的和图G~+(S)是图(S,E),满足uv∈E当且仅当u+v∈S.称一个图G为和图,如果存在一个S,使得G≌G~+(S).对于一个图G,称使得G∪r K_1是和图的最少的孤立点的个数r为G的和数.和图的概念首先是由Harary提出来的,并且他指出除了C_4的和数为3外,所有的圈C_n的和数都是2.本文研究了全部二正则图的和标号问题,证明除了C_4外所有的二正则图的和数都是2.     

完备三分图的同构分解

图G=(V,E)的边集E的一个分划{E~1,…,E~j}叫做G的一个同构分解,如果 (ii) E~j的边导出子图G~j=(V,E~j)彼此同构。G~1,…,G~j叫做G的一组同构因子,如果H≌H~j(≌表示同构),称H可分G,记为H|G。如果G的一组同构因子恰好有t个子图,称G是t可分的,或t可分G,记为t|G。如果|E|=q,t|G的一个明显的必要条件是t整除q、记为t|q。 F.Harary,R.W.Robinson和N.C.Wormald对于完备三分图K(m,n,s),当     

Harary定理的一个简短证明

关于所有(p,q)图的极大连通度,Harary找出了一个定理.本文给出这个定理的简短证明;方法是首先借助于数论中的一个引理,然后构作出两个图形以取代Harary图族中的两个;证明是用反证法给出的.     

两类图的离心图刻划

研究了网络中点与点之间的距离关系,利用算法求出循环图的离心图及其周期,并刻划了Harary图的离心图.     

关于完全s部整图

F.Harary和A.J.Schwenk(Lecture Notes in Mathematics.Berlin:Springer-Verlag,1974,406:46-51.)提出了整图的概念,即当无向图G的邻接矩阵A的特征值都是整数时,G称为整图.目前,人们已经研究了n类简单整图的性质,并得到了一些有趣的结果.运用线性代数方法证明了两个结论:设r,r1,r2,s是正整数,那么:1)完全s部图K(r,r,…,r)是整图;2)完全2部图K(r1,r2)是整图的充要条件是r1r2为完全平方数.     

完备三分图K(A,B,C)有同构因子的某些充分条件

如果图G(V,E)可以分解成t个彼此同构的边不重子图的并,则称G有t个同构因子,或者说t可分G,记为t|G。若G有q条边,t|G的一个明显的必要条件是f|q,并称之为可分性条件。 Harary,Robinson和Wormald证明了对于完备三分图当t=2,4时可分性条件是充分的,且猜测t为偶数时,可分性条件是充分的。本文证明了t=2~k时,这个猜测成立。摘     

点面图的基尔霍夫指标

图中任意2个顶点之间的电阻距离定义为将图中的每条边用单位电阻代替后所得到的电网络中这2个节点之间的等效电阻.图的基尔霍夫指标定义为图中所有顶点对之间的电阻距离之和.设G是嵌入在可定向曲面上的具有n个顶点的三角化图,在图G的每个面中插入一个新的顶点并将该点和其所在面的边界上的3个顶点之间连边,所得的图称为图G的点面图,记作K(G).本文给出了图G的点面图K(G)的基尔霍夫指标计算公式.所得结果表明,K(G)的基尔霍夫指标可以由图G的顶点数、面数以及基尔霍夫指标等参数表示.     

完全3部图的一类同构分解

本文构造性地证明，对于完全3部图 G（X，Y，Z；E），如果边数能被正整数t整除，且｜X｜, ｜Y｜和｜Z｜三个数之一也能被t整除，则完全3部图可分解为t个同构因子，从而证实了Harary “3部图猜想”的部分结论。