关于(mg+m-1,mf-m+1)-图的(g,f)-因子

讨论(mg m-1,mf-m 1) 图的(g,f) 因子问题,推广了图的因子理论问题,改进了由刘桂真和李铮得到的一些结论,有助于进一步研究(mg m-1,mf-m 1) 图的(g,f) 因子问题.     

与任意图2-正交的(g,f)-因子分解

设G是一个图，用V(G）和E(G）表示它的顶点集和边集，并设g(x）和f(x）是定义在V(G）上的两个整数值函数，且对每个x∈V(G），有4≤g(x)≤f(x)，则图G的一个支撑子图F称为G的一个（g，f）-因子，如果对每个x∈V(G)，有g(x)≤dF(x)≤f(x)。图G的（g，f）-因子分解是指E(G）能划分成边不交的（g，f）-因子，设F={F1,F2,…,Fm}和H分别是图G的因子分解和子图，若对所有1≤i≤m有|E(H)∩E(Fi）|=2，则称F和H2-正交。本文证明：若G是一个（mg m-1，mf-m 1）-图，H是G中任一有2m条边的子图，则G有一个（g，f）-因子分解与H2-正交。     

不含3正则子图的图的最大可能边数的下界

１９７４年，Ｅｒｄｏｓ和Ｓａｕｃｅｒ提出如下问题：设ｆ（ｐ）是ｐ个顶点的不含３正则子图的图的最大可能边数，确定ｆ（ｐ）。本文给出：（１）ｆ（ｐ）≥３ｐ－９，ｐ≥４；（２）ｆ（ｐ）≥３ｐ－５，ｐ≥３４。     

极大平面图的导出四正则图的三着色

本文给出了极大平面图的导出四正则图的两种构造方式、等价性及性质,证明了导出四正则图的三着色与原极大平面图四着色的一一对应关系,并且找出了导出四正则图的三种颜色与原极大平面图四着色的三组对偶二色子图之间的关系.     

图的第二个最小特征值的界

设Ｇ是ｎ个顶点的简单图，λｎ－１（Ｇ）为Ｇ的第二个最小特征值。Ｇ的非孤立点形成的图记为Ｇ１，Ｖ（Ｇ１）＝ｓ，（３≤ｓ≤ｎ）。本文主要证明了：ａ．若Ｇ１不是完全偶图，则λｎ－１（Ｇ）≤λｓ－１（Ｋ２，ｓ－２＾－ｅ），等式成立＝Ｇ１≌Ｋ２，ｓ－２＾－＾ｅ。其中图Ｋ２，ｓ－２＾－＾ｅ为完全偶图Ｋ２，ｓ－２去掉一边ｅ而得到的图ｂ．若Ｇ１既不是完全偶图，又不是Ｋ２，ｓ－２＾－ｅ，则λｎ－１（Ｇ）＜－√２／２     

关于图的圈覆盖

Ａ．Ｉｔａｌ和Ｍ．Ｒｏｄｅｈ给出了两个关于图的圈覆盖的猜想：（ｉ）任意２－边连通图Ｇ＝（Ｖ，Ｅ）有困覆盖Ｃ，使ｌ（Ｃ）≤｜Ｅ｜＋｜Ｖ｜－１；（ｎ）任意２－边连通图有困覆盖，使图的每条边至多被覆盖两次．本文证明了猜想对平面图和２－边连通没有３－边割的图成立，并给出了一与两猜想等价的条件．同时也对著名的２－圈覆盖猜想作了讨论．     

奇数度循环图的性质

本文得到了奇数度循环图是连通图的充要条件及C_n×k_2(krn/2)为循环图的充要条件,证明了三度连通循环图C_n同构于C_n<1,n/2>或C_n<2,n/2>。这一结果颇有意义。     

近双三图的两个定理

本文考虑一类有向图(一近双三图)的性质,用归纳法证明一些近双三图中存在一些特别的子图—可调形。     

超媒体系统中的语义约束问题研究

提出了一种基于数据库模式的超媒体语义网络模型,该模型通过引入模式约束图,对超媒体系统中的关系约束进行了分类,并给出了相应的约束检测算法;通过引入视图机制提出了结构约束的概念;通过扩充模式约束图的属性,描述了超媒体特定应用领域的计算约束,从而从整体上对与应用领域无关至特定应用领域的语义约束进行了深入的研究。     

几乎三角剖分图中的2—连通支撑子图

证明了每一个无可分离三角形的几乎三角剖分图均存在一个２－连通支撑子图,其最大度至多３．并且,这一结果是最佳可能的。