4个圈不交并图优美性的一些结果

讨论了4个圈不交并图3C4k∪Cn的优美性，给出了其为优美图的必要条件，并用构造性的方法给出了3C4k∪C4k 3,3C4k∪C4k 4,3C8k∪C8k-1的优美标号，证明了它们是优美的。     

r∪i=1(Pmi×Pni)的cordial性

基于图的cordial标号,给出了3个引理:cordial图G联结上一个P2×Pn图得到的新图仍是cordial图;每个图P2k 1×P2l都有2个cordial标号;至少有1个图边数为偶数或者边数都为奇数但0边之和等于1边之和的2个cordial图的并为cordial图.最后运用这3个引理证明了r∪i=1(Pmi×Pni)为cordial图.     

(Pmi×Pni)的cordial性

基于图的cordial标号,给出了3个引理cordial图G联结上一个P2×Pn图得到的新图仍是cordial图;每个图P2k 1×P2l都有2个cordial标号;至少有1个图边数为偶数或者边数都为奇数但0边之和等于1边之和的2个cordial图的并为cordial图.最后运用这3个引理证明了r∪i=1(Pmi×Pni)为cordial图.     

图C_4∪K_(m,n)的k-优美性及算术性

给出了一类非连通图C4∪Km ,n。论证了当k>1 (k∈N)时 ,该图是k优美图 ;当k >[(n - 1 )m +1 ]d +1 (d >1 ;m ,n ,d∈N)时 ,图C4∪Km ,n是 (k ,d)算术图。由此推广了文献 [7]中的一些结论。     

两类特殊图的（2,1）-全标号

研究了与频道分配有关的一种染色问题——（p,1）-全标号.（p,1）-全标号是从V（G）∪E（G）到集合{0,1,…,k}的1个映射,满足：①G的任2个相邻的顶点得到不同的整数;②G的任2个相邻的边得到不同的整数;③任1个点和与它相关联的边得到的整数至少相差p.称最小的数k为图G的（p,1）-全标号数.根据所构造图的特征,利用穷染法得到了这些图的（2,1）-全标号数.     

几类特殊图的（2,1）-全标号

研究了与频道分配有关的1种（p,1）-全标号染色问题.（p,1）-全标号是从V（G）∪E（G）到集合{0,1,…,k}的1个映射,满足：①G的任2个相邻的顶点得到不同的整数;②G的任2个相邻的边得到不同的整数;③任1个点和与它相关联的边得到的整数至少相差p.通过在2个简单图之间叠加一系列匹配构造了几类有趣图,并根据所构造图的特征,利用穷染法得到了这些图的（2,1）-全标号数.     

图Cn∪P4的优美性（Ⅱ）

本文给出了图Ｃｎ∪Ｐ４,当ｎ＝６,８,１０（ｍｏｄ１２）时的优美标号。     

C(l,k)的超欧拉性

一个含有生成欧拉子图的图称为超欧拉图.引入C(l,k)图类的概念:用C(l,k)表示一类2-边连通图,其中:l,k分别为大于零及非负的正整数,若n阶2-边连通的G属于C(l,k)即有对G中任意的边数不超过3的键E,都满足G-E的每一个连通分支都至少有(n -k)/l个顶点.在C(6,5)的基础上,利用Catlin收缩方...     

一类路不交并图的优美性

与路有关的图的优美性是人们研究的一个重点.文章讨论了形如P2m∪P2m t的两条路不交并图的优美性,用构造性的方法给出了当t=-1,1,2时的优美标号,并证明它们是优美的.     

一类序列树的构造

图G的标号指f是V（G）到整数集合的一个映射,然后边xy∈E（G）由f（x）,f（y）导出标号,仿照优美图中平衡标号的概念,定义图的序列平衡标号的概念,利用一类具有序列平衡标号的树构造更多顶点的序列树。     

一些 DNA 图的标号

为了读取DNA序列,Blazewicz等人提出了(α,k)-可标号的有向图的概念,称有向图D是DNA图若D是(4,k)-可标号的.基于此,证明了(α,k)-可标号的有向路和有向圈的充要条件.设T是一棵只有一个入(出)度为0的点的定向树,还证明了T是(α,k)-可标号的有向图的必要条件和T是DNA图的充要条件.     

一些DNA图的标号

为了读取DNA序列,Blazewicz等人提出了（α,k）-可标号的有向图的概念,称有向图D是DNA图若D是（4,k）-可标号的,基于此,证明了（α,k）-可标号的有向路和有向圈的充要条件,设T是一棵只有一个入（出）度为0的点的定向树,还证明了T是（α,k）-可标号的有向图的必要条件和T是DNA图的充要条件,     

图中k个相互独立的4-圈

通过运用图论中关于度和圈的理论知识，论证：如果σ2(G)≥6k，k∈N^ ，则图G(|G =4k)有一个支撑子图含k个相互独立的4-圈；设G=(V1，V2；E)是一个二分图，满足|V1 |=|V2|=2k，k∈N^ ，如果σ1，1(G)≥6k 1，则G包含k个相互独立的4-圈，这是对图中存在k-1个相互独立的4-圈和一条长为4的路这一结论的改进，并在一定程度上为Erdos和Faudree猜想的解决奠定了基础。     

关于图的k-因子的一个新结果

推证了命题设G是一个图 ,k是一个自然数。图G的一个k -正则生成子图称为G的一个k-因子。首先给出了一个图G有k -因子的一个充分条件 ,即若G是简单图 ,v是偶数且δ(G) v/ 2 +(k - 2 ) (这里k是整数且k 3) ,则G有k -因子。从而推广了文 [1]的一个结果 ,并得到了一个相关的结果。     

Hadamard矩阵对应图类的特征

讨论Hadamard矩阵对应的简单图类的邻接矩阵的特征及其相互关系，证明了1－4阶Hadamard矩阵对应的图只有K1、K2∪K2、K3∪K1和K4；偶图G的邻接矩阵是Hadamard矩阵充分必要条件是G＝K2∪K2。     

泛圈图的邻域并

让NC2＝min{│N（x）∪N（y）││x,y∈V（G）,d(x,y)=2│},得到的主要结果如下：对于2连通n(n≤6）阶图G,如果NC2≥n-δ,则G是泛圈图或kn/2,n/2。此结果改进了图论专家R．J．Faudree等的结果。     

平衡序列图的结构

考察了平衡序列图的结构,给出了平衡标号与序列标号的关系,提出了用二部划分确定平衡标号的方法,得到了平衡标号特征与导出边标号最小值的关系式,给出非平衡的序列树。     

一类路图的哈密尔顿圈

设G是一个图,我们用Π_k(G)表示G中所有具有k个顶点的路P_k所成之集。图G的路图P_k(G)有顶点集Π_k(G),且P_k(G)中的两个顶点相邻表示两条路P_k的并形成G中的一条路P_(k+1)或一个圈C_k。H.J.Broersma和C.Hoeda研究了路图的一些性质,并提出了两个猜想:1)若T是一颗树,△(T)≥4,则P_3(T)不是哈密尔顿图;2)若G是唯一圈图,△(G)≥5,则G不是哈密尔顿图。在本文中,我们证明了这两个猜想是对的。     

一种极大外平面图的构造法

提出了一种判定图同构的方法,其原理是赋予每个无标号极大外平面图一个n×(n-3)阶0-1矩阵.证明了矩阵与极大外平面图一一对应,矩阵相同的图彼此同构.构造所有可能的n阶极大外平面图,并用上述方法除去其中同构者,所有n阶无标号极大外平面图都被构造出来了,同时得到其总个数,解决了有关极大外平面图同构与计数问题.     

关于3-圈不重点的平面图全染色的一个结论

给定一个图G,G的全k可染色是指至多用k种颜色,对G的顶点和边同时进行染色,使得相邻的或相关联的两个元素(点和边)不染同一颜色。图G的全染色数xT(G)是指使G全k染色的最小整数k。Δ(G)是G的最大度,显然任何一个图不会是全Δ可染的,但是Vizing猜测任何一个图一定是全Δ 2可染的。而这个全染色猜想,对平面图也仍是没有得到解决的。本文利用欧拉公式和重新分配的方法,对3-圈不重点的平面图进行了讨论,得出结论:最大度Δ≥8的任何两个3-圈不重点的平面图一定是全Δ 1可染的。