有关对称无权图生成树数目的拆分定理

设G是一个对称平面图.Ciucu等证明了一个有关G的生成树数目的拆分定理,也就是G的生成树数目可用两个小图的生成树数目乘积来表示.在此基础上,提出了一种图变换,给出了图在这种变换下生成树数目的变化关系式,再结合矩阵-树定理给出了该拆分定理的一个简短证明.同时,受Zhang等证明的赋权图生成树权和的拆分定理启发,还给出了一个关于对称无权图生成树数目的等价拆分公式.     

最小度生成树的最大度算法

最小度生成树问题是一个NP难问题.给出了求最小度生成树的一个直观近似算法:找到图G的最大度,从其所在的基本圈上删掉1条与其关联的边,如此循环,直到图G的最大度不在任何基本圈上,如还有其它基本圈,删掉圈上的1条边,得到1棵生成树.这种算法得到的生成树的最大度数比最优解的度数至多大1.     

关于哈密顿图的一点注记

如果图G含有一个过G中每个顶点恰好一次的圈,则称G是一个哈密顿图。对于含有两个不相邻顶点a和b的图G,本文给出了一些条件,如果G满足这些条件,且G ab是哈密顿图,则G也是哈密顿图。     

2n阶(n-2)-正则二部图的最小基本圈基

设图G为2n阶(n-2)-正则二部图.构造了图G的一个基本圈基并且证明了此圈基就是图G的一个最小基本圈基,同时还确定了任意最小基本圈基对应的生成树的结构.     

循环群上有向Cayley图的Hamilton回

G 是一个有限群,M 是 G 的一个极小生成集。用 Cay(M:G)表示生成集为 M 的 G 上的一个 Cayley 图。Z_n 表示模 n 的剩余类加群。本文借助 Rankin 的一个引理,研究有向 Cayley 图的 Hamilton 回的存在性。作为 Rankin 引理的推论,给出了 Cay(M:Z_n)存在 Hamilton 回的若干充分条件。     

关于生成迹在闭包运算下的稳定性

证明了如果在图G的闭包中可以找到一个以某确定顶点为端点的生成迹当且仅当在G中可以找到一个以该顶点为端点的生成迹,得出了无爪图中生成迹的存在性在Ryjacek闭包运算下是稳定的,也就是一个无爪图G存在一个生成迹当且仅当图G的闭包cl(G)存在一个生成迹.     

弱哈密顿连通图关于Wiener指数，Harary指数，hyper-Wiener指数的充分条件

对于一个平衡二部图,如果任意两个不同部分的顶点可以由一条哈密顿路连接,那么该平衡二部图称为弱哈密顿连通图。在给出连通的平衡二部图的拓扑指数条件的基础上,利用Wiener指数、Harary指数和hyper-Wiener指数分别给出了平衡二部图是弱哈密顿连通的充分条件。     

平面连通图为哈密顿图的一个充要条件

本文利用对偶的概念，给出了平面连通图为哈密顿图的一个充要条件。 定理 平面连通图G（V≥3）为哈密顿图的充要条件是存在G的对偶图G＊＝（V＊，X＊）满足： （１） Ｖ＊ ＝Ｖ１＊：Ｖ２８，Ｖ１＊∩Ｖ２＊＝，Ｖ１＊≠，V２＊≠ （２）Ｖ１＊和Ｖ２＊的诱导子图＜Ｖ１＊＞和（Ｖ２＊）均是树。     

由圈基所产生的生成树

设对一个(p,q)连通图G,给定了它的一个定向,确定了线和圈的编号,对于每一个圈,选定一个方向。T是G的生成树,则G有q-p 1条弦,设为x_1,x_2,…,x_i(r=q-p 1),而且每一次添加一条弦x_i到T得到一个且只有一个圈,不妨记为C_i,则C_1,C_2,…,C_r是G的一组圈基。称这一组圈基为对应于生成树T的圈基。但是并非每一组圈基都对应一个生成树的圈基。本文将证明如果对一组圈基加适当的条件后,就能成为一个生成树的圈基。     

一些圈加边图的着色

设P(G;λ)表示图G的色多项式,若P(H;λ)=P(G;λ),称H和G色等价.设ξ是图组成的集合,若对任意图H,当H和ξ中的某一图色等价时,都有H ∈ξ,称ξ是完全色等价类.本文给出了由部分广义多边形树Gsl(a,b;c,d)(s+t=2)组成的一个完全色等价类.     

图生成树棵数的一种求法

本文提出了对给定图 G来说 ,计算它的所有的生成树棵数的一种方法 ,即由 Cayley定理与 Binet-Cauchy定理来推导一个公式τ(G) =det(KKT) ,为了证明此公式的成立 ,还证明了从一个图的完全关联矩阵 M(G)中删去任意一行后 ,得到的矩阵 K和 K的转置 KT满足 Binet-Cauchy条件。公式τ(G) =det(KKT)的证明是由一个图的生成树的棵数公式τ(G) =τ(G -e) τ(G . e)与具有以上性质的矩阵 K与 KT且 det(KKT) =∑ Ki Ki=∑K2i 合起来证明。     

不超过7阶的3-关系图的刻画

给定一个图G,如果存在一个边标号树T,使得树T的叶子集等于图G的顶点集,并且树T任何叶子x到叶子y的唯一路径上的边标号之和为3当且仅当xy为图G的边,那么称图G是一个3-关系图.该文讨论了什么样的图是3-关系图,证明了图G是3-关系图的必要条件为图G是二部图,即只要图G包含奇圈,则图G不是3-关系图.更进一步,完全刻画了圈为3-关系图的充要条件,即一个圈是3-关系图当且仅当圈为偶圈,并且给出了偶圈相对应的边标号树.最后讨论了比较小的图为3-关系图的条件,即证明了阶至多为7的图是3-关系图的充分必要条件为图G是二部图.     

完美T形树的匹配唯一性

研究了完美T形树T（l1,l2,l3)的匹配唯一性，给出了其匹配唯一的充分必要条件，定理A 设G=T（l1,l2,l3)是T形树，若l1,l2,l3至少有一对相等，则G必匹配等价于一类Q∪P型图。定理B 设G=T（l1,l2,l3)是完美T形树，则图G匹配唯一的充分必要条件是l1,l2,l3互不相等。     

双环网络G(N;1,s)等价生成树

提出研究双环网络G(N;1,s)的抽象模型--等价生成树,并对其性质进行了研究,给出了双环网络G(N;1,s)等价生成树的构造方法.提出基于等价生成树G(N;1,s)的直径d(N;1,s)的求解算法,并给出了其显式公式,利用C语言编程对等价生成树的结构模型进行了仿真.结果表明:算法不仅可在有限时间内求出G(N;1,s)的所有直径,而且可方便地得到源结点到所有其他结点的最短路径.算法的复杂度为O(N).     

一类哈密顿图的控制数的上界

设G=(V,E)是一个简单图,D是V的一个子集,如果集合V-D的任意点都与D中的点相邻,则称D为图G的一个控制集.图G的最小控制集中的点数称为G的控制数.本文对哈密顿图的控制数进行了研究,证明了命题:如果n阶图G是一个最小度为5的哈密顿图,则图G的控制数就不大于5n/14.     

2_补树图

若简单连通图G=(V,E)满足G=T_1UT_2,E(T_1)∩E(T_2)=φ,其中T_1和T_2是G的生成树,则G称为简单2—补树图.本文研究了简单2—补树图的若干性质(10个定理),其中包括:2—补树图G顶点度的性质,κ(G),λ(G),δ(G),△(G),2—补树图的构造性质和判定条件.     

用矩阵判断哈密顿图的一个充要条件

给出了一个从图的邻接矩阵来判断有限无向连通图是否是哈密顿图的充分必要条件     

树的匹配覆盖

设图G没有孤立点.图G的匹配覆盖数,记为mc(G),是指满足如下条件的最小正整数k:G有k个匹配M1,M2,…,Mk覆盖图G的所有顶点.证明了如果图G是一个树,则mc(G)∈{Δ0(G),Δ0(G) 1},其中Δ0(G)是指使得图G的某个顶点有l个一度邻点的l的最大值.而且,任给一个树G,给出了一个可以确定图G的匹配覆盖数的线性算法.     

直径不超过2的无爪图的2-因子

Gould证明了直径不超过2的无爪图G是哈密顿的,也就是说,直径不超过2的无爪图G存在一个分支的2-因子.本文通过利用图G的哈密顿性及无爪图的特点即若G是无爪图且d(u,v)=2,则N(u)∩N(v)=J(u,v),分析了图G的结构,得到了G包含两个分支2-因子的一个充分条件.     

没有7-圈的平面图的BB-染色?

研究了没有7-圈的连通平面图的BB-染色问题。应用经典的Discharging方法,证明了没有7-圈且不含相邻4-圈的连通平面图G,存在G的一棵生成树T,使得( G,T)是BB-4-可染的。这一结果进一步拓展了平面图的BB-4-可染的充分条件。