互补自中心图

在第4届国际图论会议上(1980.5 Michigan) J, AKIYAMA和F. HARARY'"综述J’满足性质p的图G及其补图G的研究现状,并指出,尚有很多性质p的问题一可提出.我们考察p是一个图的自中心性.Buckley' 2’曾指出:寻找自中心图的特征是一个十分困难的工作.Copobiancol”把它列入未解决的图论问题之一本文研究图G及其补图G的自巾心性,刻划G和G均具有白中心性的图的一系列特征,找出了构造自补自中心图的一般方法,并去构浩自巾J广。因根供一条右扮徐径_水立所论的图均县有限It nu单图。夫加说明的IN论太     

关于Menger图的几种运算

设Ｇ是一个简单连通图，若分离Ｇ的余一独立集Ｓ的最小点数等于连接Ｓ的点之间的内部不相交路的最大个数，则称Ｇ是Ｍｅｎｇｅｒ图。我们考虑了图的几种运算并给出了运算后的图是Ｍｅｎｇｅｒ图的条件。     

基回数为2的自中心图

Buckley 指出找寻自中心图的特征是一个困难的任务.作为这一工作的开始,找出一些自中心图类看来非常必要.文[1]定理3中证明当 k=■或 n≤k≤[(1/2)n(n-1)]时,n 个顶点 k 条边的自中心图存在.本文建议以基回数为出发点构造自中心图,并确定了基回数为2,即 k-n=1的全部自中心图.本文还纠正了[1]中的一个疏忽.设 G=(V,E)是简单图,u,v∈V(G),d(u,v)为 u,v,两点的距离.定义1 图 G 的半径 r(G)=(_{(v,w)}定义2 图 G 中顶点“的最远距离     

图的非自中心数（英文）

许克祥等人在文献[1]中定义了新的基于离心率的图不变量,称之为图的非自中心数(简称NSC数),记为N(G).图的非自中心数定义为N(G)=∑_({v_i,v_j}V(G)|e_i-e_j|,这里ei表示顶点vi的离心率,在文献[1]中,同其他结果一起,作者确定了一些图的N(G)数的上界和下界并且刻画了达到上下界的极图.但是作者给出的极图的刻画是不完全的.基于他们得到的研究结果,在本文中我们给出了达到上下界的所有极图的完全刻画.另外,我们还给出了阶为n直径为d的树T的N(T)数的下界并且确定双圈图和含有奇数个顶点的三圈图的NSC数的上界.     

几类基回数为3的自中心图

本文从一个基回数为2的自中心图出发,用添加链的办法,证明了构作自中心图类的一些定理,并讨论了几类基回数为3的自中心图。本文还纠正了[4]中定理证明的一个不当之处及[5]中的一个错误推论。注意到不连通图均是自中心图,本文所讨论的图均指有限的简单连通图。其他术语见[6]。     

基回数为3的自中心图的构造

本文将基回数为3的自中心图分为两类,并以简明的方式分别给出了它们的构造。     

几个图运算下的图的惯性指数的界

图的惯性指数是指三元组In(G)={i₊(G),i_-(G),i₀(G)},其中i₊(G),i_-(G),i₀(G)分别是图的邻接矩阵A(G)的正、负、零特征值的数目(包括重数).得到了包括加一个点、加一条边、剖分一条边、重合2个点、图的联等运算下图的正惯性指数的界.     

自中心树图

在电路网络的计算机分析中提出的问题之一是列出网络中的所有支撑树。因此,树图的概念被提出,并已进行了比较深入的讨论。图G的树图T(G)是这样的图:它的顶点与G的支撑树一一对应,它的两个顶点是相邻的,当且仅当G对应的支撑树之间的距离为1。     

若干运算图的倍乘赋权Harary指标

ALIZADEH等近期提出了一个修正的Harary指标,即顶点对的贡献被赋予其度的乘积.其指标被称为倍乘赋权Harary指标,定义为H_M（G）=Σ_u≠v（δ_G（u）δ_G（v））（d_G（u,v））,其中,δ_G（u）表示顶点u在图G中的度,d_G（u,v）表示2个顶点u和v在图G中的距离.给出了张量积G×K_r,强积GK_r,圈积G₁oG₂的倍乘赋权Harary指标值的精确计算公式,这些公式与图的其他不变量（如倍加赋权Harary指标、Harary指标、第1类和第2类Zagreb指标、第1类和第2类反Zagreb指标）有关.此外,利用所得结果计算了开栅栏与闭栅栏的倍乘赋权Harary指标.     

自余弱弦图

研究了一类自余(sc)弱弦图,即广义的自余弱弦图,得到了一些自余弱弦图的下边界和上边界.讨论了自余弱弦图的识别问题,特别地给出了一种O(m2)时间算法,能推断自余图是弱弦的还是非弱弦的,进一步作者编目了自余弱弦图的至少17种异体.     

一些运算图的Wiener极性指数(英文)

图G=(V,E)的Wiener极性指数定义为G中距离为3的无序点对的个数.文中给出了广义hierarchical积图、笛卡尔积图及F-和图的Wiener极性指数运算公式.同时也给出了两个图的Kronecker积图和复合图的Wiener极性指数运算公式.     

基于异或运算的逻辑函数OC展开系数图与b_j图的转换

分析了逻辑函数的OC展开式与RM展开式,利用异或运算和符合运算的性质,推导了dj展开系数与bj展开系数的关系.在此基础上提出了基于折叠异或以及基于重心的实现dj图和bj图相互转换的两种图形方法,并对这两种方法作了比较.通过实例显示,这些图形方法具有直观、有效等特点.     

一些图运算的调和指标与调和多项式的线图

本文给出了边意义下调和指标及调和多项式关于笛卡儿积、Corona积、联图、笛卡儿和以及字典积等图运算的计算公式.边意义下的该指标关于上述运算中图的若干上下界是基于凸函数积分的已知结果得到的.     

自中心的几个定理

自中心图是每个顶点都是图的中心的图.关于自中心图的一般特征,目前除了由其定义直接可以推知的图的直径等于半径这个特征之外,尚未得到其它结果.因此[1]中将这个问题作为未解决的第20个问题提了出来.本文讨论了自中心图的一些特性,同时构造了几类自中心图,它们比已知的初等圈、完全图、不连通图和完全n-部分图等自中心图更广泛,并且包含了[1]中提出的那种自中心图。本文所讨论的图G都是指有限的、连通的、无自环和无多重边的无向图,其它术语     

关于序集的幂运算和万有链

引言对两集合 X、Y,幂 Y~λ是由 X 到 Y 内的映照的全体之集。如果 X、Y 都是序集,自然地要求对 Y 也能引入适当的序关系。G.Birkhoff 和 M.Day 等人巳引入和讨论过了(见[1][2])。为了便于和本文对比,他们的定义不妨总结成如下形式。对 f、g ∈Y,f≤g 的意思是:     

基于异或运算的逻辑函数OC展开系数图与bj图的转换

分析了逻辑函数的OC展开式与RM展开式,利用异或运算和符合运算的性质,推导了dj展开系数与bj展开系数的关系.在此基础上提出了基于折叠异或以及基于重心的实现dj图和bj图相互转换的两种图形方法,并对这两种方法作了比较.通过实例显示,这些图形方法具有直观、有效等特点.     

若干运算图的倍乘赋权Harary指标（英文）

ALIZADEH等近期提出了一个修正的Harary指标,即顶点对的贡献被赋予其度的乘积.其指标被称为倍乘赋权Harary指标,定义为H_M(G)=∑u≠vδ_G(u)δ_G(v)/d_G(u,v),其中,δ_G(u)表示顶点u在图G中的度,d_G(u,v)表示2个顶点u和v在图G中的距离.给出了张量积G×K_r,强积G■K_r,圈积G_1oG_2的倍乘赋权Harary指标值的精确计算公式,这些公式与图的其他不变量(如倍加赋权Harary指标、Harary指标、第1类和第2类Zagreb指标、第1类和第2类反Zagreb指标)有关.此外,利用所得结果计算了开栅栏与闭栅栏的倍乘赋权Harary指标.     

关于五点图的多部图设计

讨论了完全多部图的G设计的存在性,其中G是五点四边图和五点五边图。并给出其存在谱。     

关于图的强协调值

引言文[1]中,D.Frank Hsu引入了强协调标号(strongly harmonious labelings)的定义:设G是一个n边图,如果存在一个映射φ:V(G)→{0,1,…,n}满足i)φ是单射; ii)Auv∈E(G),令φ(uv)=φ(u)+φ(u),有{φ(uv)|uv∈E(G)}={1,2,…,n},则称G为强协调的,φ为它的一个强协调标号,简称为强协调值。显然,φ导出了一个E(G)与{1,2,…,n)的一一对应。本文的目的,一是求出全体n条边的图的所有强协调值的个数;二是指出几类非强协     

关于定向图的PLD序列

<正> 图的PLD序列的概念首先是由M·F·Gapobiance于1970年引进的。现在我们把图的PLD序列的概念推广到定向图中去,同时给出出树(或入树)、圈图等的单侧PLD序列,并推广图的P_i性质于定向图。