k-正则图中第二大特征值和最小特征值的界

运用n阶矩阵B=(b_(ij))≥0的第二大特征值的结果,结合图论的背景,得出了n阶k-正则图G的第二大特征值θ_2(A(G))≤k-(?){|N_i∩N_j|},最小的特征值θ_n(A(G))满足:θ_n(A(G))≥-1-(?){k-|N_i∩N_j|-1,k- |N_i∩N_j|+1}.

k-正则图的可扩性质

设 G是 k正则 (k-1) -边连通的简单图 ,F是 G的一个边集且 | F|≤ k-1。本文证明了如下结论 :如果 G有完美匹配 ,则 G-F也有完美匹配。于是 ,我们推出 :如果 G有完美匹配 ,则 G是 1-可扩图。

一类k-正则图的生成树数目与熵

若图G的一个生成子图T是一棵树,则称T为G的一棵生成树;若T为森林,则称它为G的一个生成森林.生成树是表征网络结构性质的一个重要物理量,网络中生成树越多,则网络越健壮.提出了一个k-正则图构成的小世界网络模型,介绍了其概念及演化过程,计算了k-正则图的相关拓扑特性,例如直径、聚类系数等,给出了此类k-正则图的生成树数目计算方法,得出生成树数目公式及熵.

k-正则偶图对集矩阵的分解定理

证明了一个ｎ阶非负实矩阵可分解为某些ｎ阶置换矩阵的线性组合的定理，由此得到了ｋ－正则偶图的对集矩阵的分解定理．这些定理及其证明给出了ｋ－正则偶图的完美匹配的构造方法，并举例说明对集矩阵的分解不是唯一的．

(k,k-1)-双正则图的平衡Judicious Partitions(英文)

Bollobás和Scott提出猜想:任意一个边数为m且最小度大于1的图存在顶点集的平衡二部划分使得每一部分点集的导出子图包含的边数不超过m/3.Bollobás和Scott证明了绝大部分正则图存在顶点集的平衡二部划分使得每一部分点集的导出子图包含的边数比m/4小.这里讨论(k,k-1)-双正则图的平衡二部划分,证明了每一个(k,k-1)-双正则图存在平衡二部划分使得每一部分点集的导出子图包含的边数是m/4左右.

阶数最小的k—正则强协调图

本文利用构造法给出了k—正则强协调图(k=1,2,…,8)的最小阶数.

含K_5的10点K正则图的团覆盖数

首先自定义了点的可互换性,在此基础上证明了10点k-正则图中最大团为K5,并对k的不同取值进行了讨论,得出了含有最大团K5的10点k-正则图的团覆盖数.

正则图的谱性质

文章就正则图的谱性质进行讨论,给出了正则图的线图,相关矩阵的相互关系及其特征值的范围。

(4d+1)-正则图中的2d-因子

设d是一个正整数 ,G是一个 (4d +1 ) -正则图 .证明了若图G不含d +4条割边 ,则G有2d 因子 .进而说明上述结果是最好的 .

3-正则3-边可着色图的极大扩容图的整数流

研究了3-正则3-边可着色图的无限扩容图的边色数,并获得Tutte的4-流猜想成立的无限类。

正则图的距离标号数的上界

图的距离标号问题是近30年来研究比较活跃的一个标号分支,最初源于对无线网络中频率分配问题的一种抽象描述,同时它也是图论中经典图着色理论的自然推广,具有重要的理论意义与应用价值.文章主要研究k-正则图的L(h_1,h_2)标号数,通过利用Lovsz局部引理,给出了k-正则图的距离标号数的上界.

二分图为k-消去图的 2个条件(英文)

图G的一个k 正则支撑子图称为G的k 因子 .若对G的任一边e ,图G总存在一个k 因子不含e ,则称G是k 消去图 .若图G存在一个划分 (X ,Y)使得G的每条边的端点分别在X和Y中 ,则称G =(X ,Y)为二分图 .证明了二分图G =(X ,Y)且X =Y是k 消去图的充分必要条件是kS≤r1+2r2 +… +k(rk+… +rΔ) -ε(S)对所有S X成立 .并由此给出二分图是k 消去图的一个邻集充分条件 .

图的全控制数和匹配数的可比较性

设tγ(G)为G的全控制数.证明了:(1)对广义θ-图G,tγ(G)≤α(G)+1;(2)对任意k-正则无爪图G,k≥3,有tγ(G)≤α(G).这里α(G)表示G的匹配数.作为结果(2)的推论,对k-正则无爪图(k≥3),证明了Favaron猜想是成立的.即对最小度不小于3的简单图,有tγ(G)≤12 V(G).此外,举例说明了当图的最小度不超过2时,对一般图而言,匹配数与全控制数不可比较.

两类H-cordial图的构造(英文)

给出了图G是H-cordial图的一个必要条件,证明了基于两个正则图而构造的新图G*是H-cordial图,从而得到了两大类H-cordial图的构造方法,由此可推导出一系列图都是H-cordial图.

图论中Berge最大独立集和Lovasz两个猜想的反例

本文通过对图论中的 C.Berge 最大独立集猜想和L.Lovasz 猜想的研究,提出了一些实际例子说明这两个猜想在所给的条件下是不能成立的。

关于亚循环2-群的对合交换图

对合交换图是以群中二阶元共轭类为顶点,两顶点有边当且仅当它们交换的图.

恰有2个内度的2维Torus网络的定向图

设G是一个简单图且D是G的一个定向图.若对D中任意顶点x,d-(x)=a或b,则称G是[a,b]可实现的.主要研究了2维Torus网络中[a,b]可实现的充要条件.设H=Torus(p,k)是一个2维Torus网络,其中p和k是2个不小于3且奇偶性相同的正整数.设0≤a,b≤4,则H是[a,b]可实现的当且仅当存在非负整数s和t使得s+t=kp且as+bt=2kp.

两类冠图的符号罗马控制数

设图G=(V,E)为一个简单无向图,若S?V,则记f(S)=∑v∈sf(v)。若实值函数f:V→{-1,1,2}满足以下两个条件:1) 对于任意的顶点v∈V,均有f(N[v])≥1成立;2) 如果对任意顶点v∈V,若f(v)=-1,则存在一个与v相邻的顶点u∈V满足f(u)=2,则称该函数为图G的符号罗马控制函数。图G的符号罗马控制数定义为γsR(G)=min{f(V)|f为图G的一个符号罗马控制函数}。本文利用构造法及穷标法主要得到了k-正则图的冠图以及轮图的冠图的符号罗马控制数的精确值。

两类特殊图的符号星控制数

针对“关于图的符号星控制数”一文中有一个定理(关于完全图的符号星控制数)的部分结果是不正确的,文章给出正确的结论及其证明,并确定了k-正则二部图的符号星控制数。

自同构群作用下具有两个轨道的连通图的连通性(英文)

若连通图G在自同构群作用下具有两个轨道V1和V2且满足|V1|=|V2|;G[V1]是k-正则图;G[V2]是r-正则图且G[V1V2]是l-正则图,则K(G)≥min{k,r}+1.构造的例子表明上述结果是最好可能的.