关于Euler生成子图极大边数的一个注记

若图G存在欧拉生成子图,则称G是超欧拉图(supereulerian).常用SL表示全体超欧拉图组成的集合 设G是有n个点的简单图,G∈SL,如果δ(G)≥ 4且δ≥n5-1,则G存在欧拉生成子图H,使得 |E(H) | / |E(G) |≥ 3/5     

一类α-子图

根据相关文献中给出的用以寻找欧拉生成子图极大边数的有效工具α-子图的概念,证明了对于任意G ∈ SL,Kl,m(l≥3,m≥3)是G的1-min{l,m}/1-子图.     

子立方图的2-距离严格邻点可区别边染色

2-距离严格邻点可区别边染色是指图G有一个正常边染色,且任意2个距离为2的顶点的颜色集合互不包含.2-距离严格邻点可区别边色数是指使图G有一个2-距离严格邻点可区别边染色的最小颜色数值,记作χ^′_2-snd(G).采用反证法证明了：若图G是子立方图,则χ^′_2-snd(G)≤7.     

一类循环图的色数

循环图具有很强的对称性,作为有价值的通讯网络拓扑已受到广泛的关注。研究了一类循环图Ｃｎ〈１,ｋ〉,完全确定了其色数。     

一类极大临界h连通图的性质

设G是h连通图，图G的顶点υ称为临办点，G－υ不再h连通，如果G的每个顶点都是临界的，则称G为临界h边连通图。对于G中任意两个相邻的项点x与y，G＋xy不再临界h连通，则称G为极大临界h连通图。引入图的粘合的概念，讨论了δ（G）＝3h／2－1的极大临界h连通图的性质，得到了这类图有关原子，最小点割和分支的重要性质，这有利于进一步研究这类图的结构。     

图的极大匹配并行算法

对一类无向图的边极大匹配问题,在ＥＲＥＷ ＰＲＡＭ并行计算模型上,给出Ｏ（ｌｏｇｎ）时间、使用Ｏ（ｎ＋ｍ）／ｌｏｇ ｎ）处理器的最佳、高速并行算法。     

简单图的子图及其性质研究

给出图论中关于子图的定义,并得到子图的一些性质。通过定理阐述子图与其导出子图的同构性、子图与哈密尔顿图的关系,并证明和举例。     

图的色数与其补图边色数的关系

本文对图的点色数与其补图边色数的关系进行了考察.     

生成子图与图的哈密顿性质

主要证明了以下结果；１．如果Ｇ是一个连通的无爪的非哈密顿图，则Ｇ至少有一条长为２δ＋的路。２．如果Ｇ是一个２连通的无爪图，且δ（ｐ－２）／３，则Ｇ是可迹的。３．Ｇ是一个２连通的无爪图，且不含生成子图Ｂ工Ｇ１，如果Ｇ的每个朵匀于Ｚ２的生成子图都满足ψ（α１，ｂ１）ˇψ（α１，ｂ２），则是Ｇ是泛圈图。     

一类α-子图

根据相关文献中给出的用以寻找欧拉生成子图极大边数的有效工具α-子图的概念,证明了对于任意G∈SL,Kl,m（l≥3,m≥3）是G的1-1/min{l,m}-子图．     

立方图的Turán结果

本文主要研究立方图的Turán结果,以及对立方图的最大二部子图的探讨。     

立方图的Turán结果

本文主要研究立方图的Turán结果，以及对立方图的最大二部子图的探讨。     

2和3连通图中的禁止子图与哈密顿性质

证明了如下结果：（１）若Ｇ是２－连通的（Ｋ１，３，Ｐ５，Ｂ）－自由图，或２－连通的（Ｋ１，３，Ｚ２，Ｐ５）－自由图，则Ｇ是哈密顿图，（２）若Ｇ是３－连通的（Ｋ１，３，Ｚ１）－自由图，或３－连通的（Ｋ１，３，Ｚ２，Ｐ５）自由图，或３－连通的（Ｋ１，３，Ｐ５，Ｂ）－自由图，则Ｇ是哈密顿连通的。     

图是极大限制边连通的一个充分条件

设G是n阶简单无向连通图,G的限制边割是删除它以后G不连通,且留下的每个分支不含孤立点的边子集;限制边割的最小基数称为限制边连通度.记G的顶点x的度为d(x)。证明了若对超级连通图G中任意一对不相邻的顶点x和y都有d(x) (dy)n,则G是极大限制边边通的当且仅当G不同构一种特殊图G。     

变换图G~(-+-)的极大边连通性

对任意图G=(V(G),E(G)),其变换图G-+-的顶点集为V(G)UE(G),顶点α和β在G-+-中邻接当且仅当下列条件之一成立:当{α,β) E(G)时,α和β在G中不邻接或不关联;当{α,β} E(G),α和β在G中邻接.证明了所有连通的变换图G-+-都是极大边连通图.     

极大欧拉生成子图为Hamilton圈的图

对极大欧拉生成子图为Hamilton圈的图作了初步研究,得到了该类图的极大欧拉生成子图的边数问题,在一定条件下满足3/5—猜想,并给出了一个公开问题;同时也得到了该类图的最小度及最大度的上界.     

无爪图的极大欧拉生成子图边数问题

研究了无爪图的极大欧拉生成子图边数问题,给出了当其最小度不小于4,且去掉极大欧拉生成子图后图的分支数不小于顶点数的1/4时,catlin-猜想成立;进一步得到了最大度不小于5时,超欧拉无爪图的极大欧拉生成子图一定不是Hamiltion圈的结论.     

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

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

图的极大匹配并行算法

对一类无向图的边极大匹配问题,在ＥＲＥＷＰＲＡＭ并行计算模型上,给出Ｏ（ｌｏｇｎ）时间、使用Ｏ（（ｎ＋ｍ）／ｌｏｇｎ）处理器的最佳、高速并行算法