关于边染色临界图的独立数

1968年,Vizing提出猜想:边染色临界图的独立数不大于其阶数的一半.针对不含2度点的边染色临界图,本文证明当最大度为9,10时,独立数α(G)≤(3△-3)/(5△-3)|V|和当△∈{11,…,46}时,独立数α(G)≤(15△-42)/(23△-42)|V|.     

3-临界图独立数的一个结果

1968年,Vizing提出了关于临界图的独立数猜想：若G是n阶的Δ-临界图,则有α（G）≤n/2.利用Vizing邻接引理研究这一猜想,给出了3-临界图的一个上界.     

关于图的边染色方面的一些结果

改进了一些边染色临界图的边数的下界。同时证明了：对没有４－圈或任何两个３－面都不同时关联于一个点的平面图，关于边染色的平面图猜想成立。     

关于图的边染色方面的一些结果

改进了一些边染色临界图的边数的下界．同时证明了：对没有４圈或任何两个３面都不同时关联于一个点的平面图,关于边染色的平面图猜想成立．     

临界图独立数的上界

1968年,Vizing猜想,对于n阶的△临界图G,其独立数a（G）≤n/2．利用著名的Vizing邻接引理和Fiorini不等式的证明方法,证明了如果临界图G的一个最大独立集中主顶点个数不超过1,则猜想成立,从而改进了Luo等的一个结果．     

关于临界图性质的一个结论

图的边色数是指对图的边进行染色使得任意两相邻边染不同的颜色所需要的最少的色数.1965年,Vizing证明了任意最大度是Δ的图的边色数或者是Δ或者是Δ 1.若为前者,则称图是第一类的,否则称为第二类的.若G为连通的第二类图,且对G的任意边e,有χ′(G-e)<χ′(G),则称图G为Δ临界图.对于临界图的性质的研究有助于对图的分类问题的研究.本文给出了如下定理:G是一个Δ临界图,x是G中的一个Δ点,如果|N4(x)|=3,那么对u∈N4(x),N≤Δ-1(u)=φ.     

Halin图的均匀边染色

图G的一种均匀k-边染色是指用k种颜色去染G的边使得对G的每一个顶点v，任何两种颜色染与。相关联边的数目最多相差1．证明了对任意的大于3的整数k，Halin图都有均匀k-边染色；讨论了k=3的情况．     

图的无圈边染色的一个结果

为了研究简单图G的无圈边染色,利用线性一时间算法思想证明了最大顶点度为4的简单图G。如果G中任意一条边的两个端点的度数之和不超过6,则其无圈边色数不超过5。     

图染色数的一个结果

图Ｇ的染色数Ｘ（Ｇ）是使得Ｇ中任何相邻两点均染不同色的最小颜色数。文中证明了，如果ω（Ｇ）≥６，△（Ｇ）＝ω（Ｇ）＋１，ㄧＶ（Ｇ）ㄧ≤２ω（Ｇ）＋１，则Ｘ（Ｇ）＝ω（Ｇ），给出了两个图Ｇ０，Ｇ１，使得ㄧＶ（Ｇ０）ㄧ＝１４，ω（Ｇ０）＝６，△（Ｇ０）＝７，Ｘ（Ｇ０）＝７；ㄧＶ（Ｇ１）ㄧ＝１１，ω（Ｇ１）＝５，△（Ｇ１）＝６，Ｘ（Ｇ１）＝６。     

Halin 图的均匀边染色

图G的一种均匀k 边染色是指用k种颜色去染G的边使得对G的每一个顶点v ,任何两种颜色染与v相关联边的数目最多相差 1.证明了对任意的大于 3的整数k,Halin图都有均匀k 边染色 ;讨论了k=3的情况     

关于临界图的若干结果

Ｖｉｚｉｎｇ’ｓ猜想：ｎ阶Δ－临界图的边数ｍ满足ｍ≥（ｎΔ－ｎ＋３）／２。本文证明了当ｎΔ＝３时猜想也成立以及当５≤Δ〈ｎ／２，ｎΔ＝４时猜想也成立。同时给出了临界图的两个新的性质。     

关于图的可达划分数

本文给出了E.J.Cockayne和S.T.Hedetniemi的下列猜想的一个新证明:当图G的团图为2-分图时,G的最小团的阶数不大于G的可达划分数;讨论了图的可达划分数与连通度的关系。     

外平面图的边面 List 染色

设Ｇ是无割点平面图，ｘｅｆｌ（Ｇ）为Ｇ的边面Ｌｉｓｔ选择数。本文证明了若Ｇ为最大度Δ（Ｇ）≥６的无割点外平面图，则ｘｅｆｌ（Ｇ）＝Δ（Ｇ）。     

关于图的同构不动边

图G的一条边e称为G的同构不动边,如果G—e+e’≌G当且仅当e’=e.若e=uv是G的同构不动边,那么对G—e的任意自同构映射π有π({u,v})={u,v}.图的同构不动边反映了二元关系系统中的定性关系,改变这种关系将改变系统的结构.这种关系的存在对系统的重构有重要的意义.本文中猜想:几乎所有的图含同构不动边.为支持这个猜想,列出了所有不含同构不动边的树形图和单圈图.     

图多项式以及图的不同特征根个数

设G是具有邻接矩阵A的简单图,P(x)是有理系数多项式,如果P(A)是某个图的邻接矩阵,我们记这个图为P(G)。我们考虑这样的问题:给一个图G,什么样的多项式P(x)给出一个图P(G)?这个图是什么样的图?当G是星图时,本文对上述问题给出完全的回答。然后,还导出一个连通正则图的不同特征根个数的新的下界。     

若干图联图的边联结数

本文研究了路、圈、完全图相互间经过联运算以后所得图的边联结数,得到了Lm(?)Ln,Cm(?)Cn,Lm(?)Cn,Lm(?)Kn和Cm(?)Kn的边联结数的计算公式,这里Lx,Cx,Kx分别表示有x个点的路、圈、完全图。     

图的全色数强色数和点荫度

利用图标的方法得到图的全色数的一个上界，并证明其是可达的。其次给出图的强色数的一个上界，并对极图予以刻划，最后对图与补图的点荫度之间的关系给出一个简单的证明。     

一类HAMILTON图中圈的数目

Yap H P和Teo S K提出问题:下述等式是否成立?m(K)=(1/2)(k+1)×(k+2),M(k)=2~k+k。此外,对于任意介于m(k)与M(k)之间的整数i,是否存在G∈H(n,k)使得f(G,k)=i?本文解决了上述问题。     

第Ⅰ类图的若干性质

本文证明了第Ⅰ类图的一个充要条件，得到了第1类图的一些性质。     

几类图的联结数

本文给出了若干完全图的联(nK_r+mK_s),圈、路和完全二部图分别与完全图的补图的字典式积(C_m(K_n)、L_m(K_n)和K_(a,b))以及完全r—部图(K_(n1,n2,…nr))等几类图的联结数。