de Bruijn—Good图D_n~3的强同态

de Bruijn—Good 图(下面简称 D—G 图)在非线性移位寄存器与编码理论中应用较为广泛.对这种图,以前在二元域上研究较多.近来对有限域上的一般情况引起了人们的注意.万哲先、刘木兰确定了 k=2情况下 D—G 图的全部6个2—1同态.我们对 k>2的一般情况引入了强同态的概念,并证明了若干基本定理.利用这些基本定理,我们有可能找到 D—G 图的全部强同态.由于强同态的数目随 k 的增大增长极快,所以,受计算机容量与速度的限制,只能对较小的 k 得出具体结果.本文给出了我们利用计算机得到 k=3情况下 D—G 图的全部强同态.     

基回数为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-因子的简便算法

本文给出一种产生全部排列的算法.这种方法先定义一个工作数组B,根据它的变化规律,确定交换集合中哪两个元素可以得到另一个排列.对此算法略加修改,便可用来产生1-因子,1-因子连通以及求全符号网络函数等.     

超能整循环图的构造

图G的能量E(G)定义为图的特征值的绝对值之和.如果图G的能量E(G)2n-2,则具有n个顶点的图G称为超能图;如果它是循环群上的Cayley图,即其邻接矩阵是一个循环矩阵,则称其为循环图.整循环图是指循环图的特征值全为整数.基于Ramanujans和,利用Euler函数和Mobius函数,讨论了整循环图的超能性.同时,利用Cartesian积图给出了一个构造超能整循环图的方法.     

关于全图补图的完美匹配

G是一个简单图,变换图G---是G的全图的补图.证明了对于给定的一个图G,G K1 K2,G---有一个完美匹配的充要条件是V(G) E(G)是偶数.     

具有给定阶和最大度的单圈图的最大匹配能量

图的匹配能量由UTMAN等于2012年提出,定义为图的匹配多项式的根的绝对值的和. 如果一个连通图的边数与点数相等, 或有唯一的一个圈,则称为单圈图.刻画了在具有给定阶与最大度的所有单圈图中达到最大匹配能量的图.     

超连通图的充分条件（英文）

设G是一个连通图.图的连通度κ(G)存在一个最小正整数k,使得FV,|F|=k且G-F不连通或是一个平凡图.如果每一个最小点割都孤立G的一个点,则图G是超连通的或超-κ的.定义没有孤立点的图G的逆度为R(G)=∑v∈V1/d(v).得到:设n阶连通图G,最小度为δ,若R(G)1+2/(δ+1)+(n-2δ-1)/((n-1)(n-3)),则G是超-κ的.     

变换图G++-的超力连通性

对于图G,一般有λ(G)≤δ(G).如果λ(G)=δ(G),称图G是较大边连通的.如果G的每一个最小边割只能分离G的一个孤立点.称图G是超边连通的.本文证明了几乎所有的有限图G,其变换图G -都是超边连通的.     

具有给定阶和最大度的单圈图的最大匹配能量（英文）

图的匹配能量由GUTMAN等于2012年提出,定义为图的匹配多项式的根的绝对值的和.如果一个连通图的边数与点数相等,或有唯一的一个圈,则称为单圈图.刻画了在具有给定阶与最大度的所有单圈图中达到最大匹配能量的图.     

单演半群的Γ图

对半群Cayley图的研究是近年来十分活跃的研究领域.定义了半群的Cayley图的一种推广图Γ图,刻画了单演半群的Γ图的结构,给出了单演半群的Γ图弱连通的一个充分必要条件.     

具有最小Wiener指数的三圈图

一个连通图的Wiener指数定义为图中所有点对的距离之和.主要研究了三圈图Wiener指数的下界问题,并刻画了达到下界的极值图.     

基于改进分解图计算布尔函数e-导数、c-导数及布尔导数的方法

提出了基于改进分解图(D图)同时计算布尔函数的1阶、2阶e-导数、c-导数及布尔导数的方法,讨论了当布尔函数的变量数为偶数(即n=2k)时,计算k阶及k阶以下全部e-导数、c-导数及布尔导数所需的D图数.与传统方法相比,该方法显著减少了D图数,且简单、有效、易于计算机编程操作.     

线团图的一些性质

B.Hedman在文[1]中介绍了构造线团图的一个算法.本文用这一算法得到了线团图的一些性质.它们涉及到图的连通度、直径和色数.     

具有最小Wiener指数的三圈图（英文）

一个连通图的Wiener指数定义为图中所有点对的距离之和.主要研究了三圈图Wiener指数的下界问题,并刻画了达到下界的极值图.     

3正则平面图的哈密顿圈

将一个图表示在一个平面上使各边除顶点外没有公共点时,称为平面图.如果平面图G含有通过所有顶点的圈(哈密顿圈),则称G为平面哈密顿图.研究化学结构的图形,尤其是3-正则平面图,确定它是否哈密顿图是个令人感兴趣的问题.Tait曾猜想每个3-正则3-连通的平面图都是哈密顿图.Tutte首先构成3-正则3-连通的反例,以后又有些人作出其他反倒,其中仿Tutte图构成的Lederberg图,具有38个顶点.     

关于图的最大特征根的若干定理

设 G 是简单图.A(G)是 G 的邻接矩阵,A(G)是非负的对称阵,其特征根全是实数,故必有最大特征根.文献[2]中讨论了图的最大特征根(以下简称大根)的某些变化规律,进行了这方面的研究.本文将继续讨论图的大根问题.主要结果是:1、给出图的大根变化规律的一个一般性定理.此定理类似于文献[3]的定理.运用它可以推广文献[2]中结果到更一般的情形.2、给出一个以一定方式联出某些子图而构成的图类的大根变化规律.     

一类单圈图的最大Hosoya指标(英文)

一个图的Hosoya指标Z(G)定义为图G的所有的边独立集数目之和.让Mn标记圈上所有点的度数不小于3的满载单圈图.本文将分别描述出满载单圈图的第一大和第二大Hosoya指标及其极图特征.     

Harary图的外连通度(英文)

一个顶点集是一个Rg-点割,如果它将一个连通图分割成一些连通分支使得每个连通分支至少含有g个顶点.图G的g-外连通度(记作κg(G))是Rg-点割的最小基数.图G的通常的点连通度和上连通度分别相应的为κ0(G)和κ1(G).本文将分别证出第一类和第二类Harary图的κg和刻画它们的Rg-点原子部分.     

Cartesian积与邻点可区别着色之间的关系（英文）

图G的一个正常k-边着色是指k种颜色1,2,…,k对图G各边的一个分配,使得任意2条相邻边染以不同的颜色.对于图G的一个正常边染色f和G中任何一个顶点x,Sf(x)或S(x)表示与顶点x关联的边在f下的颜色所构成的集合.若对于图G中任意2个相邻顶点u和v,有S(u)≠S(v),则称f为图G的邻点可区别正常边染色.对图G进行邻点可区别正常边染色所需的最少颜色数,称为G的邻点可区别正常边色数,记为χ′a(G).图G的一个正常k-全染色是指k种颜色对图G的顶点和边的一个分配,使得任意2个相邻的或相关联元素染以不同的颜色.对于图G的一个正常全染色g和G中任何一个顶点x,使用Cg(x)或C(x)来表示顶点x的颜色(在g下)以及与顶点x关联的边在g下的颜色所构成的集合.若对于G中任意2个相邻顶点u和v,有C(u)≠C(v),则称g为图G的邻点可区别全染色.图G的邻点可区别全染色所需的最少颜色数称为图G的邻点可区别正常全色数,记为χ″a(G).主要讨论了Cartesian积和2种邻点可区别染色之间的关系.     

Cartesian积与邻点可区别着色之间的关系

图G的一个正常k-边着色是指k种颜色1,2,…,k对图G各边的一个分配,使得任意2条相邻边染以不同的颜色.对于图G的一个正常边染色f和G中任何一个顶点x,S_f（x）或S（x）表示与顶点x关联的边在f下的颜色所构成的集合.若对于图G中任意2个相邻顶点u和v,有S（u）≠S（v）,则称f为图G的邻点可区别正常边染色.对图G进行邻点可区别正常边染色所需的最少颜色数,称为G的邻点可区别正常边色数,记为χ'_a（G）.图G的一个正常k-全染色是指k种颜色对图G的顶点和边的一个分配,使得任意2个相邻的或相关联元素染以不同的颜色.对于图G的一个正常全染色g和G中任何一个顶点 x,使用C_g（x）或C（x）来表示顶点x的颜色（在g下）以及与顶点x关联的边在g下的颜色所构成的集合.若对于G中任意2个相邻顶点u和v,有C（u）≠C（v）,则称g为图G的邻点可区别全染色.图G的邻点可区别全染色所需的最少颜色数称为图G的邻点可区别正常全色数,记为χ″_a（G）.主要讨论了Cartesian积和2种邻点可区别染色之间的关系.