二部完全图为H2-cordial图的充分必要条件

在图的Hp-cordial系列问题中,有关H-cordial的讨论较多,而图的H2-cordial性结果,目前仅涉及完全图与轮.为此,在引入二部完全图的边标号矩阵表示法后,给出了二部完全图是H2-cordial图的充分必要条件.     

完全二部图优美性质探索

图论的二部图及其标号在实际应用中较多,尤其最近图标号被应用于新型的图形密码设计.首先构造出了组合完全二部图与串联完全二部图,发现了一种叫做奇边魔幻全标号的标号,并给出了组合完全二部图具有奇边魔幻全标号的证明.此外,得出了串联完全二部图是优美图、(k,d)-优美图的结论.     

几乎完全二部图的距离标号边跨度

研究几乎完全二部图(即完全二部图K_(n,n)去掉一个1-因子)的L(1,1)和L(2,1)边跨度.基于图的L(1,1)跨度确定了L(1,1)边跨度.通过给出具体标号得到图的L(2,1)边跨度的上界,进而利用反证法确定了L(2,1)边跨度的确切值.     

一类特殊对称图的边魔幻性

边对称图〈H,G〉含有子图H和G,使得删去边子集E(H)的所有边后,剩余图的任何分支均同构于G.刻划了一类对称图的基本性质,推广边魔幻全标号到广义边魔幻全标号.利用可算法化的构造性证明,得到大型的具有(广义)边魔幻全标号的对称图.     

不超过7阶的3-关系图的刻画

给定一个图G,如果存在一个边标号树T,使得树T的叶子集等于图G的顶点集,并且树T任何叶子x到叶子y的唯一路径上的边标号之和为3当且仅当xy为图G的边,那么称图G是一个3-关系图.该文讨论了什么样的图是3-关系图,证明了图G是3-关系图的必要条件为图G是二部图,即只要图G包含奇圈,则图G不是3-关系图.更进一步,完全刻画了圈为3-关系图的充要条件,即一个圈是3-关系图当且仅当圈为偶圈,并且给出了偶圈相对应的边标号树.最后讨论了比较小的图为3-关系图的条件,即证明了阶至多为7的图是3-关系图的充分必要条件为图G是二部图.     

几类图的2-强边染色

研究了树、圈、完全二部图和轮图的2-强边染色问题.对于树,给出了2-强边色数等于最大顶点度加1的充分条件;对于圈、完全二部图及轮图,求出了2-强边色数,并给出了相应的染色方案.     

几类图的Signless Laplacian特征多项式

对于一个简单图G,称矩阵Q（G）=D（G）＋A（G）是图G的Signless Laplacian矩阵,多项式QG（λ）=det（λI—Q）是图G的特征多项式。本文给出了在完全二部图K2,a-2上两种不同的加边方式所得图类和在C3的一个顶点上悬挂P=n-3条边所得图类的Signless Laplacian矩阵特征多项式。     

用秩1矩阵矫正法计算两类图的生成树数

设P是完全二部图K_m,n的一个匹配，本文用秩1矩阵矫正法给出了完全二部图K_m,n中包含P中的所有边和不包含P中边的生成树数目公式的一个简单证明.     

笛卡尔乘积图Cn×P2的边幻和标号及其算法

对边幻和标号的概念及其性质进行了深入研究,探讨了笛卡尔乘积图的边幻和标号.并以此为基础,证明了对?n≥3且n≡1(mod 2)笛卡尔乘积图Cn×P2存在边幻常数C1＝＋、边幻常数C2＝＋、边幻常数C3＝＋三种边幻和标号的算法.本文的结果推广了现有的一些结论.     

完全二部图全着色的构造

利用全着色矩阵给出完全二部图全着色的构造,该构造可以方便快捷对完全二部图进行全着色.     

一类完全多部图的Hamiton性刻画

Gutin证明了在强的半完全二部图中若含有一个由两个圈构成的圈因子,则图是Hamilton图。把此定理推广到无向图中就可得到这样一个结果,即含有一个由两个圈构成的圈因子的完全二部图是Hamilton图。在此基础上,对含有由两个圈构成的圈因子的完全n（n≥3）部图进行了讨论,得出了类似于二部图的结果。     

关于完全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(m,n)-A中的色正规图类

设Ｐ（Ｇ,λ）表示简单图Ｇ的色多项式。简单图Ｈ称为与Ｇ是色等价的（记作Ｈ￣Ｇ）,如果Ｐ（Ｈ,λ）＝Ｐ（Ｇ,λ）。简单图类Ｌ称为色正规图类,若对任意Ｈ,Ｇ∈Ｌ使Ｈ￣Ｇ都有Ｈ与Ｇ同构。     

完全偶图的补图的特征根分布

设Ｇ为ｐ 阶连通简单图,其补图Ｇ为完全偶图Ｋｎ,ｍ 及空图Ｋ的并,笔者利用完全偶图的谱的特性,获得了图Ｇ的特征根分布     

循环图C_(2n)(1,4)的偶匹配可扩性

称图G是偶匹配可扩的,是指G的每一个偶匹配M都可以扩充为G的一个完美匹配.判定图是否是偶匹配可扩的是co-NP-完全问题,根据图的k-偶匹配可扩性完全刻画了循环图C2n(1,4)的偶匹配可扩性.     

关于k-优美图一个猜想的证明

二分图是一类有着广泛应用的图,但这类图并不都是优美图,因此需要进一步深入研究它的优美性。本文根据马克杰教授提出的猜想:完备二分图Km,n的冠是k-优美图(m≤n,k≥2),利用构造法证明了当m=1或m=2,k≥2时,猜想成立;当m≥3,k≥(m-2)(n-1)时,猜想成立。拓展了k-优美性的研究范围。     

强笛积图的边联结数

本文研究了强笛卡尔积图的边联结数，求得了路与路、路与圈、圈与圈、路与完备图、圈与完备图、路与完备偶图、圈与完备偶图、完备图与完备图、完备图与完备偶图、完备偶图与完备偶图的强笛卡尔积的边联结数。