边愉快图研究的一些结果

边愉快图是新近提出的研究课题，本文给出了边愉快图的必要条件和一类添加图或删边图成为边愉快图的充分条件；考察了几种常见图类的边愉快特征；构造了一类奇阶偶正则的边愉快图，给出了相应的边愉快标号方法；提出了值得进一步研究的一些问题。     

正则图的均匀边染色

研究正则图的均匀边染色,指出并非所有正则图都存在任意种颜色的均匀边染色.证明当l能够分解为整数k与偶数b的乘积时,l-正则图存在均匀k-边染色.同时,给出正则图均匀边染色的最小颜色数.     

关于图的减边控制

引入了图的减边控制的概念,给出了一个图G的减边控制数γ′m(G)的两个下界,确定了完全图、圈和轮图的减边控制数,并提出了若干未解决的问题和猜想.     

有悬挂边的圆柱面格子图的K──优美性

研究了有悬挂边的圆柱面格子图的Ｋ—优美性问题，证明了所有图＜Ｐ＿ｍ，Ｃ＿ｎ＞（ｍ＞１）是Ｋ—优美的。     

外接多边形的极限

提出了外接n边形的概念，证明了外接n边形序列的极限是正n边形。     

奇圈图 Cn 的边幻和标号及超边幻和标号算法

设计了对任意自然数n(n≥3)且n=1(mod 2)的奇圈图的边幻和标号和超边幻和标号算法,证明了得到的所有奇圈图既是边幻和图,也是超边幻和图.     

Halin图的均匀边染色

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

关于等价边优美边裂图

引进等价边优美边裂图的概念,阐述了等价边优美边裂图的存在性及其等价分类研究的方法.     

关于图的同构不动边

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

外接多边形的极限

提出了外接n边形的概念 ,证明了外接n边形序列的极限是正n边形     

若干强积图及合成图的邻点可区别一般边染色

讨论了若干满足某些条件的两个图的强积图以及合成图的邻点可区别一般边色数的若干结论, 并在此基础上得到了PnC2m+1, C2nFm, C2nW2m+1, PnFm, PnW2m+1, C2n+1C2m+1, Pn［C2m+1］, C2m+1［Pn］, C3［C2m+1］, C2m+1［C3］ 等图类的一般邻点可区别边色数。     

图的点可区别无圈边色数的一个上界(英文)

图G的一个正常边染色f,若满足:1)G中无2-色圈;2)对于V(G)中的任意两点u和v,有C(u)≠C(v),这里C(u)={f(uw)|uw∈E(G)},则f叫做图G的一个点可区别无圈边染色.图G的点可区别无圈边色数,记为χ′_(vda)(G),是图G的一个点可区别无圈边染色所用色的最小数目.证明了若图G是一个最小度不小于5,且顶点数不超过30Δ~4的图时,χ′_(vda)(G)≤10Δ~2,其中Δ是图G的最大度.     

关于近似二部图边覆盖染色的一个充分条件

设G是一个简单图，其顶点集为V(G) 而边集为E(G) . S∈E(G)称为G 的一个边覆盖，如果由S 导出的子图是G 的一个生成子图. G 的边覆盖色数χ’c(G) 是E(G) 所能划分成的最大边覆盖数. 已知 δ-1≤χ’c(G)≤δ ，由此将 χ’c(G)=δ的图称为CⅠ类图，否则称为CⅡ类图. 显然，图的边覆盖染色分类问题是NP-完全的. 给出了近似二部图是CⅠ类图的一个充分条件，而且该条件中的下界是最好的。     

联图P_3∨K_(m,n)和C_4∨K_(m,n)的邻强边色数

设计一个具有分支限界技术的算法来研究联图P3∨Km,n和C4∨Km,n的k-邻强边染色,并证明mn-3时它们的邻强边色数均为m+n+3.     

图的边添加和减少

用P（t,d）（或者C（t,d））表示从一条长为d的简单路（或者简单圈）通过添加t条边后得到图的最小直径.证明了：如果t和d满足条件t≥4且t＋4≤d≤t＋7,或者t=4且d=10k＋1（k≥1）,那么P（t,d）=[d-2D＋1]＋1.对某些t和d,确定了C（t,d）的值和最好下界,部分地解决了Schoone等的猜想[J.GraphTheory,1987,11：409-427].     

关于路与偶圈的6个广义Ramsey数的值

给出求R(G1,G2,G3)的一个算法,并利用它得到6个广义Ramsey数的值:R(P4,C4,C4)=9,R(P4,C4,C6)=9,R(P4,C6,C6)=9,R(P5,C4,C4)=11,R(P5,C4,C6)=9,R(P5,C6,C6)=11.     

Wm V C3的点可区别正常边色数

对于轮和圈的联图，给出了一种点可区别的边染色方法，并得到了其点可区别边色数．     

图K2n\E（Fm）（n≥4,m≥2）的点可区别边染色

对简单图G(V,E),设f是从E(G)到{1,2,…,k}的映射,k为自然数,如果f满足:1)对任意的uv,uw∈E(G),v≠w,有f(uv)≠f(uw);2)对任意的u,v∈V(G),u≠v,有C(u)≠C(v).则称f为图G的k-点可区别边染色法,而最小的k被称为点可区别边色数(其中C(u)={f(uv)|uv∈E(G)}).研究了图K2n\E(Fm)(n≥4,m≥2)的点可区别边色数.     

基于边分类的三维模型外轮廓线抽取算法

根据三维模型面片的方向性对边进行分类，筛选出轮廓边即共享可见面与不可见面的边，大幅度地排除那些不可能成为轮廓线的边，筛选过程只是一种比较运算。算法L利用外轮廓线的连通性递归搜索邻接的轮廓边得到若干闭合回路和分离的轮廓边，最终得到外轮廓线，并且自动决定的闭合回路方向和回路之间位置关系决定了回路是否属于外轮廓线；对那些精度不高而可能造成闭合回路搜索失败的三维模型，算法C利用遮挡关系由模型的前向面片对轮廓边进行裁剪得到三维模型的外轮廓线。用四叉树结构对模型投影区域进行划分，尽可能地排除那些不可能对轮廓边有遮挡关系的前向面片，减少裁剪的比较范围，降低算法的复杂度。本文的方法快速准确，适应各类二维流形模型。     

无K4-子式图的2-距离和可区别边染色

图G的一个正常边染色φ若满足:∠u,v∈V(G),且d_G(u,v)≤2都有f(u)≠f(v),其中f(u)=∑_uw∈E(G)φ(uw),则称φ为图G的2-距离和可区别边染色。运用反证法,结合构造染色函数法,研究了无K₄-子式图的2-距离和可区别边染色,确定了无K₄-子式图的2-距离和可区别边色数的一个上界。