平面格图的圈数

设f(m,n)和f(m,n)分别是平面上m×n格图的圈数和长为2l的圈数。本文给出f(3,n)的递推公式,f(2,n)的闭公式和f(m,n)的递推式阶的上界估计。     

连通图中圈数

用|V（G）|、|E（G）|和f（G）分别表示图G的顶点数、边数和圈数．设F（k）＝｛f（G）;G是满足|E（G）|－|V（G）|＝k的无环连通图｝,n（k）＝minF（k）和N（k）＝maxF（k）．证明了下述结果：（1）n（k）＝k＋1;（2）N（k）≤2k+1;（3）对每个整数k≥1,N（k）≥2k＋k（k－1）＋1且当1≤k≤4时等式成立;（4）对每个整数k≥1是奇数时,N（k）≥2k3;当k≥2是偶数时,     

m×n平面格图圈计数的一些结果

该文讨论了 2×n平面格图实长为 2 ,实宽为k的平面格图圈的计数 ,得到一般的计数表达式f(k) =- 2 12 [(1- 2 ) k 1 (1 2 ) k 1 ]。进而讨论一般的m×n平面格图圈的计数 ,得到一些结果。     

联图的消圈数

设图G=（V,E）,对于V中任何一个点集S,若G-S是一个无圈图,则称S是图G的一个消圈集,且称min{|S||S是图G的消圈集}为图G的消圈数,记为Φ（G）.本文考虑联图的消圈问题,得到了几类联图消圈数的精确值.设G_m和G_n分别表示阶数为m和n的简单连通图,则联图G_m∨G_n的消圈数满足:min{m,n}≤Φ（G_m∨G_n）≤min{m+Φ（G_n）,n+Φ（G_m）}.本文中几类联图的消圈数证实了上述不等式的上界是紧的.特别地,当G_m和G_n都为树时,可由不等式直接得到Φ（G_m∨G_n）的精确值.     

关于路Pn和圈Cn的幂图的消圈数

讨论关于路Pn和圈Cn的幂图的消圈数.对于任意给定的次幂m,文中得出了路Pn和圈Cn的幂图的消圈数的准确值.另外,还给出了路Pn和圈Cn的幂图的最大导出树.     

非广义多边形路的2连通图的圈数

若Ｇ中一条路Ｐ的每个内点ｖ 都有ｄＧ（ｖ）＝ ２,则称Ｐ为Ｇ的简单路⒀一个２ 连通可平面图Ｇ称为广义多边形路,如果用下述方法得到的图Ｇ是路：对应于Ｇ的每个内部面ｆ （Ｇ是Ｇ的平图）有一个Ｇ的顶点ｆ,Ｇ的两个顶点ｆ和ｇ在Ｇ中相邻当且仅当Ｇ中相应的两个内部面的边界交于一条Ｇ的简单路⒀令ｊ＝ ｜Ｅ（Ｇ）｜－ ｜Ｖ（Ｇ）｜和ｍ （Ｇ）为Ｇ的含圈数⒀论文证明了下述结果：设Ｇ是非广义多边形路的２ 连通图,则ｍ （Ｇ）≥ｊ２＋ ５ｊ２ － １⒀     

Halin图的消圈数及点染色问题

Tutte关于3-连通图的结构定理表明:每一个3-连通图都可由某个轮图(也是Halin图)经顶点分裂逐步得到.这表明了Halin图在图结构研究中的地位和作用.首先研究得到了近正则Halin图的消圈数的上、下界并证明了上述界是紧的,接着得到了最大度为k或最小度为k的Halin图的消圈数所满足的界;此外还研究了Halin图的点染色问题,给出了它的点色数定理的一个新证明.     

路与圈的叉积图的消圈数

研究了路与圈的叉积图的消圈数.对一般的路Pm和圈Cn,得到了Pm×Cn的消圈数的一个紧的下界;对一些特殊的Pm路和圈Cn,得到Pm×Cn的消圈数的准确值.     

路与圈的笛卡尔乘积图的消圈数

探讨路与圈的笛卡尔乘积图的消圈问题,对一般的路与圈,根据引理1及推论1推导出它们的笛卡尔乘积图的消圈数的一个紧的下界;进而对一些特殊的路与圈,推导出它们的笛卡尔乘积图的消圈数的准确值.     

平面格图生成树的计数

设ｔ（ｍ,ｎ）和ｔ（ｍ,ｎ）分别是平面ｍ×ｎ格图生成树和对称生成树的数目,从而给出了ｔ（３,ｎ）和ｔ（３,ｎ）的闭公式以及ｔ（ｍ,ｎ）递推式阶的估计．     

蛇形图的消圈公式

本文讨论了任意形状蛇形图的消圈数,给出每节都是4-圈情形的蛇形图别名函数C(H),并证明每节为4-圈的蛇形图的消圈数等于它的别名函数的势.另外,在保持消圈数不变的情况下,通过简单的收缩、剖分运算把求解任意情形的蛇形图的消圈数问题归为求解每节都是4-圈特殊情形下的蛇形图消圈数问题.     

完全图与树、圈、完全图、完全二部图的笛卡尔乘积图的消圈数

主要讨论了完全图与树、圈、完全图及完全二部图的笛卡尔乘积图的消圈数,并得到了它们的笛卡尔乘积图的消圈数的准确值.     

整数的平面分拆格

在整数平面分拆集合Ｐ中定义了序关系及∨和∧运算；证明了在所定义的序关系及运算下Ｐ为局部有限的分配格，给出了该格上链分解及Ｍｏｂｉｕｓ函数；最后得出了Ｐ的某些截断的结构及最长链的个数。     

三正则平面图与平面三角剖分图

探讨三正则平面图的路与平面三角剖分图 Hamilton圈的关系 ,给出平面三角剖分图 Hamilton圈的一个充分条件及算法     

轮图在平面上的圈基结构性质

利用代数的思想、拓扑的方法研究了平面上轮图的圈基结构.证明了轮图的圈基所具备的一系列性质,提供了求平面上图的圈基的方法与途径.从而推广了Josef Leydold,Peter F.Stadler等人的研究结果.     

图格的定义与性质研究

本文定义了一种偏序关系将图与格的有关知识联系起来了,给出了图格的定义,并进一步分析和证明了图格的部分性质.     

一类部分格图的全染色

C.N.Campos和C.P.de Mello已经求出了最大度为0,1,2,4以及最大度为3的特殊部分格图的全色数。本文主要研究了另一类部分格图的全染色。     

平面三次图哈米尔顿性的一个充要条件

本文证明平面三次图Dg有哈米尔顿圈的充分必要条件是与之对偶的极大平面图g有树树型四着色．即Dg的对偶极大平面图g有四着色C，该四着色的某组对偶二色子图Gk的两个分支都是树．据此得到求出图Dg全部哈米尔顿圈的算法，该方法已经成功处理了批量例图．     

平面三次图中的二元哈米顿圈

本文定义了平面三次图中的二元哈米顿圈,并证明了:平面三次图Dg有二元哈米顿圈,充分必要的是,与之对偶的极大平面图g有树-圈-树型四着色,更具体地说是,与图Dg对偶的极大平面图g有四着色C,该四着色的某组对偶二色子图:Gk=RUS,其中R连通并且仅仅包含一个圈;S有两个分支,并且都是树.据此,得到求出图Dg全部二元哈米顿圈的算法.该方法已经成功处理了批量例图.     

δ>2极大平面二分图间的关系

本文讨论δ>2极大平面二分图之间的关系,证明了 B_(mn)每一图可由其任一图经改边得到.