关于完全二部图的几种标号

1.引言　随着计算机的发展,图的标号在网络和通讯等领域中的应用越来越广泛,而图的各种标号这些年已发展到许多种,其中优美标号和协调标号的研究比较活跃.本文将对一类特殊的图,讨论其各种标号.     

一类定向完全二部图的秩

图谱理论是代数图论和组合矩阵论中重要的研究领域,图所对应的各类矩阵是图谱理论的重要研究方向和研究内容.本文主要根据邻接矩阵,将图D的秩r(D)定义为邻接矩阵的秩,基于完全二部图K_2,n的定向图,即每条边x_i～y_j都被赋予一个定向：x_i→y_j或x_i←y_j,通过导出子图及孪生点的相关定理,刻画了这类定向完全二部图的秩.     

完全三部图k(m,n,r)色唯一性的几个结果

令K(m ,n ,r)表示完全三部图 ,本文证明了 :1.若k≥ 0 ,l≥ 0 ,m >k2 -k(l+1) +l(l- 1) +2 (k2 -kl+l2 ) 1 2 ,则k(m ,m+l,m +k)是色唯一的 .2 .若k≥ 0 ,l≥ 0 ,m -k≥ 2 ,m -l≥ 2 ,m >2 (k2 -kl+l2 ) 1 2 +k2 -k(l- 1) +l(l+1)3,则k(m -k ,m -l,m)是色唯一的 .3.若k≥ 0 ,l≥ 0 ,m >2 (k2 +kl+l2 ) 1 2 +k(k +1) +kl+l(l- 1)3,则k(m -k ,m ,m +l)是色唯一图 .4 .若k≥ 0 ,l≥ 0 ,m -k≥ 2 ,m >2 (3k2 +l2 ) 1 2 +3k2 +l(l- 1)3,则k(m -k ,m +l,m +k)中色唯一的 .本文也推广了文 [1]推论中所涉及的几类完全三部图的色性的结论 .     

完全二部图的边优美性

研究了完全二部图及其局部边迁移图的边优美性．主要结果有：当（m,n）=1时,奇阶完全二部图K(m,n)为边优美图的充要条件是m＋n|mn＋1．     

完全二部图的边优美性

研究了完全二部图及其局部边迁移图的边优美性.主要结果有:当(m,n)=1时,奇阶完全二部图K_(m,n)为边优美图的充要条件是m+n|mn+1.     

完全二部图的边优美性

研究了完全二部图及其局部边迁移图的边优美性,主要结果有：当(m,n)=1时,奇阶完全二部图Km,n为边优美图的充要条件是m n|mn 1。     

关于二部图Km,m的若干性质

本文讨论了二部图Km,m的性质,其中一个性质说明,Ore(奥尔)在1960年提出的图G是Hamilton图的充分条件,当图G是二部图时其充分条件可减弱.     

完全t部图的色唯一性

设P（G,λ）是图G的色多项式,若对于任意与图G的色多项式相等（P（G,λ）=P（H,λ））的图H都与图G同构（G≌ H）．则称图G是色唯一图;这里通过比较t部图的t十1类的划分数,证明了若     

两个完全二部图的匹配和的L(2,1)-标号

研究了两个均同构于完全二部图Km,n的图G1=(X1,Y1)与G2=(X2,Y2)的匹配和Bm,n的L(2,1)-标号问题,得到了下面的结果:(1)若X1中元素完全与X2中元素相匹配且m,n>3,则Bm,n的L(2,1)-标号数为m+n;(2)若X1中元素不完全与X2中元素相匹配且m,n>6,则Bm,n的L(2,1)-标号数为m+n+1.     

关于二部图Km,m的若干性质

本讨论了二部图Km,m的性质，其中一个性质说明，Orc(奥尔）在1960年提出的图G是Hamilton图的充分条件，当图G是二部图时其充分条件可减弱。     

亚完备二分图的算术性

图的算术性是图的一个重要性质,有广泛的应用．文章给出亚完备二分图的算术标号。并证明亚完备二分图是（k,d）-算术图．这一结果丰富了图的算术性理论,也为研究其它图类的算术性提供了有价值的参考．     

完全图上的沙堆模型

文章主要讨论完全图上沙堆模型,首先给出了列举完全图常返构形所有元素的一个算法,并利用此算法列出了K3、K4、K5上的所有常返构型;然后得出了完全图上沙堆模型的高度分布函数的具体表达式。     

一种五点图的填充和覆盖

设图G0是由一个三角形和一条边所组成的五点四边图（G0＝K3＋K2）,本文运用“带洞的图”[1],确定了完全图Kv的图G0填充数和覆盖数。     

基于最小生成树的图论模型及其在医学中的应用

样本数据分类是医学研究中常见的工具。本文提出了一种新的数据分类思想和方法。在分析分类过程及其主要矛盾的基础上，提出了极大λ-截子图的概念。作为示范，建立了三个基于最小生成树的图论模型，并分析了其在研究营养与疾病的关系以及基因分类中的应用。最后讨论了图论在医学中的应用前景。     

完全图的边带宽的另一证明

图G的边的一个标号f是指边集E（G）到自然数的子集的一个一一映射。图G的边带宽为B’（G）=minB＇f（G）,B＇f（G）是G的所有邻边的标号f的差的绝对值的最大者。本文确定完全图Kn的边带宽：当n=3,4时，B＇（Kn）=2n-4；当n≥5时，B＇（Kn）=n（n-5）/2＋7。     

完全二部图k_(4,n)去掉两条边的交叉数

用km,n表示完全二部图,用k4,m\e1,e2表示完全二部图k4,n去掉两条边e1、e2.本文确定了K4,n\e1,e2的交叉数为州z(4,n)-2[n/2]+2.K4,n\e1,e2.     

关于完全多部图K_n(t)的{C_4,C_5}——强制分解

关于完全多部图K_n(t)的C_k分解,到目前为止,已经取得了一系列的研究成果。K_n(t)的{C_i,C_j}—强制分解是指将K_n(t)分解为长为i或j的圈,并且分解中至少有一个长为i和j的圈。本文证明了多部图K_n(t)的{C_4,C_5}—强制分解存在的必要条件也是充分的。     

N阶k正则图的递归生成

研究了任意N阶k正则简单图的生成法则,提出了由简单完全图递归生成任意N阶k正则图的方法．     

最小生成树算法及其应用

Kruskal算法和Prim算法是求最小生成树的常用算法,文中设计了这两种算法的C语言程序,并通过实例说明了算法的应用.