Harary图的k-偶匹配可扩性

设图G是一简单的且有完美匹配的连通图.称图G是k-偶匹配可扩的,是指G的每一个基数不大于k(1≤k≤(V(G)-2)2)的偶匹配M都可以扩充为G的一个完美匹配.本文主要刻画了Harary图的k-偶匹配可扩性:对于任意的n,如果r(r>4)是偶数,那么Hr,2n是2-偶匹配可扩的等等.     

关于Sn＋Fn和Sn＋Wn的均匀全染色

对于图G的正常k-全染色f称为G（V,E）的k-均匀全染色,当且仅当任意2个色类中的元素总数至多相差1.χet（G）=min{k｜G有k-均匀全染色}称为图G的均匀全色数.利用均匀边染色的相关结论,讨论并得到了图Sn＋Fn和Sn＋Wn的均匀全色数.     

两类特殊图上的k-平衡标号

k-平衡标号是关于顶点数为p,边数为q的图G的一个映射f:V(G)∪E(G)→[p+q],使得在这个映射下,存在一个整数k满足uv∈E(G)都有f(u)+f(v)=k+f(uv)成立.本文提出了可生长标号的概念,主要介绍了对枝树及一类特殊的二级分叉树上的k-平衡标号,猜想任何一个(p,q)-图,若其存在k-平衡称号,则存在可生长k-平衡称号.     

一种构造k-色临界图的方法

图G的色数Х（G）是指对图G进行着色并使相邻顶点具有不同颜色的最少颜色数,若对G的任意真子图H有Х（H）〈Х（G）=k,则称G是k-色临界的,因此可以给出一种构造k-色临界图的方法。     

不含3-圈和4-圈的平面图的列表均匀染色

任意给定图G的一个k-一致列表L,若G是L-可染的,且满足每种颜色至多在「｜V（G）/k｜」个点上出现,则称G是k-均匀可选择的．若图G有一个正常k-顶点染色满足任两个色类中的顶点数至多相差1,则称G是k-均匀可染的．应用discharge方法讨论了不含3-圈和4-圈的平面图的结构,证明了对于不含3-圈和4-圈的平面图G,当k≥{max△（G）,6）时,G是k-均匀可选择的,同时G也是k-均匀可染的．     

有关满着色的一些结果

图G=(V,E)的一个正常k-着色实际上是将G的顶点划分为独立集,记为∏={V1,V2,…,Vk}.其中Vi,i=1,2,…,k,也称色类.对于任一色类Vi中的点v,如果它与其余色类中至少一个点相邻,则v被称为是满色的.如果在G的一个正常k-着色中,所有点都是满色的,则称这样的着色是满着色.如果一个图存在满着色,定义图的满着色数为使得图存在满着色的最小颜色数,记为χf(G).另外,记ψf(G)为使图存在满着色的最大颜色数.本文主要研究了有关满着色的一些性质,并给出一个满着色与完美图之间的结论.     

k-消去图的邻集和最小度

研究了为保证一个图G是k-消去图,G所具有的独立集邻集的基数和最小度。     

关于图的点强全着色

图G(V,E)的一正常k-全着色σ称为G(V,E)的一个k-点强全着色,当且仅当ν∈V(G),N[ν]中的元素着不同颜色,其中N[ν]={u|νu∈E(G)}∪{ν}。并且χνsT(G)=min{k|存在G的一个k-点强全着色}称为G(V,E)的点强全色数。本文得到了一些特殊图的点强全色数χνsT(G),并提出猜想:对于简单图G,有k(G)≤χνsT(G)≤k(G) 1,这里k(G)是文中给出的一个新的参数。     

关于图的瑕边着色

图G=(V,E)的一个(λ,β)-瑕k-边着色是一个从E到{1,2,…,k}的映射,且存在一个最小整数β≥1,对每一个色j∈{1,2,…,β},至少存在一个顶点uj∈V(G)使得顶点uj关联着有色的j条边;对每一个色l∈{β+1,…,k},没有两条相邻边着有色l.图G的(λ,β)-瑕色数被表示为χ(λ,β)(G),它是一个最小的整数,使对整数k≥χ(λ,(β)G),图G总有一个(λ,β)-瑕k-边着色.在这篇文章中,我们证得χ(λ,1)(G)+λ-1≤χ′(G)≤χ(λ,1)(G)+,其中χ′(G)是G的正常边色数,并确定了几个特殊图类的瑕色数.     

围长较大的平面图的全染色的一个结果

图G的一个k全染色是用k种颜色对图G的顶点集和边集进行染色使得相邻接的或相关联的元素染不同的颜色,图G的全色数χ＂（G）为图G的k-全染色中的最小k值.Behzad和Vizing猜想任意简单图G的全色数都不超过Δ（G）＋2,已经证明了此猜想对最大度不是6的平面图成立,而且最大度不小于9的平面图G的全色数为Δ（G）＋1.本文利用差值转移方法研究了最大度小于9的一些情况,证明了最大度为4,5,6,7,8的平面图G,如果其围长不小于8,则其全色数也为Δ（G）＋1.     

四角系统的Z-变换图的Hamilton路

如果G表示一个四角系统,则G的Z-变换图Z(G)指如下定义的图:图Z(G)的所有顶点对应于四角系统G中的所有完美匹配,且Z(G)中的两个顶点有一条边相连当且仅当它们在G中对应的两个完美匹配的对称差恰好形成G的一个四角形.利用图同构的方法,证明了两类四角系统(L-四角系统和Z-四角系统)的Z-变换图必含有一条Hamilton路.     

图拟拉普拉斯矩阵的最大特征值

图谱理论是图论研究的重要理论之一,G=(V,E)为有限无向简单图,A(G)和D(G)分别表示G的邻接矩阵和度对角矩阵.Q(G)=D(G) A(G)称为图G的拟拉普拉斯矩阵,它是图谱理论的研究对象.本文利用G的顶点数,边数,最大度,最小度以及非负矩阵理论给出Q(G)的最大特征值的新的界值估计.     

细分图的零维数

设A(G)为简单图G的邻接矩阵。图G的零维数定义为A(G)中0特征值的重数,记为η(G)。S(G)表示非平凡图G的细分图。本文讨论细分图的零维数并分别给出树、单圈图和双圈图的细分图的零维数。     

广义Mycielskian图的超连通性

Mycielski引入了对于图G的一类新的变换图μ（G）,称为G的Mycielskian.这类变换图的推广是广义Mycielskian图μm（G）,m是正整数.如果每个最小点割（最小边割）孤立G的一个点,则称图G是超连通的或超-κ（超边连通的或超-λ）.证明结果显示：设G是连通图且｜V（G）｜≥3条件下,μm（G）是超-κ的充要条件是δ（G）＜（m＋1）κ（G）;μm（G）是超-λ的充要条件是G（≠）K2,即G不是一条边.     

关于单圈图的Wiener指数

一个连通图G的Wiener指数W（G）是指图G中所有顶点对之间距离之和。主要研究单圈图去掉一条割边后其Wiener指数的上界和下界问题,并刻画了达到上界和下界的所有极图。     

分数ID-消去图的邻域并条件

若删除G中任意一个独立集后得到的图依然是分数（g,f,m）-消去图,则称G为分数ID-（g,f,m）-消去图．将若干个关于分数消去图邻域并条件的结论推广到分数ID-消去图,证明了如下两个结论：1）阶为n的图G满足n≥12k＋6m-11,6（G）≥n/3＋k＋m,且／NG（x）UG（y）/≥2n/3对G中任意一对不相邻的顶点x,y都成立,则G是分数ID-（k,m）-消去图;2）若δ（G）≥（an/2a＋b）＋（b2（i-1）/a＋2m,n〉（（2a＋b）[i（a＋b）＋2m-2]）/a,且/NG（x1）u…uNG（x1）/≥（a＋b）n/2a＋b,对V（G）的所有独立集{x1,……,xi}都成立．则G是分数ID-（g,f,m）-消去图．     

残柱体的排斥和数

图G的排斥（整）和数ε（G）（ξ（G））是使得G∪nK1是排斥（整）和图的非负整数n的最小值．证明了任何图的排斥和数与排斥整和数都相等;图Cn×K2称为棱柱．将棱柱上下底面的边Cn（称为缘边）进行一次剖分,形成的网称为残柱体．并证明了残柱体的排斥和数等于4．     

笛卡尔积图Tn×Cm的交叉数

两个图G1和G2的笛卡尔积图G1×G2定义为如下的图：V（G1×G2）=V（G1）×V（G2）,E（G1×G2）={（u1,u2）（v1,v2）｜u1=v1且u2v2∈E（G2）,或者u2=v2且u1v1∈E（G1）}．图的交叉数是图论中的一个重要拓扑参数,而确定图的交叉数是一个完全胛一问题．本文确定了若干树Tn（n≤4）与圈Cm的笛卡尔积图的交叉数．     

关于树的几个结果

树在图论研究以及复杂网络研究中常常用到.记号nd(G)表示图G中顶点度数为d的顶点的数目.本文利用树T的1度顶点个数可以由公式n1(T)=2+△(G)+D(G)n+1.对平面图G,它的面数(G)满足2(G)=4+d3Σ(d-2)n(dG).     

两个图的冠的秩

设G_1和G_2分别是n阶与m阶顶点互不相邻的简单图,G_1G_2称为G_1与G_2的冠,是通过将G_2复制n个后,把G_1的第i-个顶点与G2的第i-复制的每一个顶点相连而得到的图。本文讨论了一些特殊图类的冠的邻接矩阵的秩,主要是当G2为完全图,完全二部图,Petersens图和CP(k)时两个图的冠。