Erd(o)s-sòs猜想的一个结果

借助图的包装理论,证明了当k=n-3时,Erd(o)s-Sòs猜想(如果G是一个有g条边的,n阶简单图,并且q>1/2 n(k-1),则G包含具有k条边的所有树)成立.     

竞赛图满足(A)dám猜想的一个充分条件

对于竞赛图G=(V,A),证明了如果存在一弧xy满足条件:(1)y到x有长度为2的路径;(2)x到y没有长度为2的路径,则反向弧xy后G中圈的个数减少,即G满足(A)dám猜想.     

竞赛图满足(A)dám猜想的一个充分条件

对于竞赛图G=(V,A),证明了如果存在一弧xy满足条件:(1)y到x有长度为2的路径;(2)x到y没有长度为2的路径,则反向弧xy后G中圈的个数减少,即G满足(A)dám猜想.     

具有特定分解集的图的Turán数

主要研究了具有特定分解集的图的Turán 数,通过确定图F 的极值图,从而确定ex (n,F) 的精确值.具体来说,确定了通过将P₂∪P₃ 的每条边都用一个3团代替(其中每个团的新顶点都是不同的)而得到的图F₁ 的极值图,证明ex (n,F₁) ;确定了通过将完全二部图K_2,3 中的每条边都用一个5 长圈代替(其中每个圈的新顶点都是不同的)而得到的图F₂的极值图,证明ex (n,F₂)     

路与圈的积图的(d,1) 全标号

研究了路与圈的积图的(d,1) 全标号问题,并给出了路与圈的积图的(d,1) 全标号数。     

无线电信道分配问题的Gr(o)bner基法

计算理想的约化Gr(o)bner基,得到了一种录求最佳信道数及最佳信道分配方案的方法;即如果图M是k-可分配的,但当1≤l＜k时,图M不是l-可分配的,那么k即为最佳信道数;通过计算理想的约化Gr(o)bner基G,得到最佳信道分配方案.     

完全二部图K10,n(10≤n≤90)的点可区别E-全染色

图G的一个E-全染色f是指使相邻点染以不同颜色且每条关联边与它的端点染以不同颜色的全染色。对图G的一个E-全染色f,一旦∠u,v∈V(G), u≠v,就有C(u)≠C(v),其中C(x)表示在f下点x的颜色以及与x关联的边的色所构成的集合,则f称为图G的点可区别的E-全染色,简称为VDET染色。令χ^e_vt(G)=min{k|G存在k-VDET染色},称χ^e_vt(G)为图G的点可区别E-全色数。利用分析法和反证法,讨论并给出了完全二部图K_10,n(10≤n≤90)的点可区别E-全色数。     

广义Jacobsthal数及其组合意义

引入了广义k阶Jacobsthal序列的概念,得到了k-Jacobsthal序列的发生函数以及相关的组合恒等式.通过研究两种格路的计数,给出了k-Jacobsthal数的两种组合解释.     

关于n阶完全图的5色K_4问题

设Kn是具有n个顶点的完全图,f(n)是满足下列条件的最小正整数对于任意的正整数m≥f(n),存在Kn的一个m边着色,使得K中的任一个K4至少含5种颜色.Erdos和Gyárás给出了f(n)的上下界2/3n＜f(n)＜n;并且证明了f(9)=8.唐在[3]中证明了f(10)=9;并且改进了f(n)的下界f(n)＞2/3n+1.作者进一步改进了f(n)的下界当n≥20时,f(n)＞1/8(6n-5),同时证明了f(11)=10.     

C(P')系对幺半群的刻画

设S是幺半群。借助环模理论的方法,在S-系范畴中引入了C(P')系。通过C(P')性质主要刻画了P(P')幺半群、周期幺半群的结构特征,进而推广了C(P)系的一些重要结果,对进一步研究正则性质在S-系中的作用具有重要意义。     

基于拉普拉斯度的k-均匀超图的图熵极值

基于一般图中图熵的定义,定义了超图基于拉普拉斯度的图熵.将简单图的图熵的一些结论推广到k-均匀超图.利用一种移边操作,分别确定了在k-均匀超树、单圈k-均匀超图、双圈k-均匀超图和k-均匀化学超树中基于拉普拉斯度的图熵最大值和最小值,并确定了相应的极值图.     

笛卡尔乘积图的k-路点覆盖

对于一个图G和一个正整数k,若图G中任意一条阶数为k的路都至少包含集合S⊆V(G)中的一个顶点,那么集合S就为图G的一个k-路点覆盖。最小的k-路点覆盖基数记为ψ_k(G),为图G的k-路点覆盖数。研究圈图分别与圈图、完全图及完全二部图做笛卡尔乘积图的k-路点覆盖,得到ψ_k(G)相关的精确值和上下界。     

无4-圈和5-圈的平面图的k-frugal列表染色

在图G的一个正常点染色c中,对于图中任意一点v,如果每种颜色在点v的邻点中至多出现k-1次,这个染色就称为图G的一个k-frugal染色。关于无4-圈和5-圈的平面图的k-frugal列表染色问题,有以下两个结论:(1)对于一切不含4-圈和5-圈的平面图,如果其最大度满足Δ≥3k+8,其k-frugal列表色数小于等于「Δ/(k-1)+2;(2)一切不含4-圈和5-圈的平面图,则其k-frugal列表色数小于等于「Δ/(k-1)+5。     

k-连通图中生成树和完美匹配上的可收缩边

给出了k-连通图生成树和完美匹配上的可收缩边数目,得到如下结果:任意断片的阶都大于「k/2的k-连通图中生成树上至少有4条可收缩边;若该k-连通图中存在完美匹配,则完美匹配上至少有「k/2+1条可收缩边。     

一类稀疏图的邻和可区别边色数

设φ为图G的正常k-边染色。 对任意v∈V(G),令f_φ(v)=∑_uv∈E(G)φ(uv)。 若对每条边uv∈E(G)都有f_φ(u)≠f_φ(v),则称φ为图G的k-邻和可区别边染色。 图G存在k-邻和可区别边染色的k的最小值称为G的邻和可区别边色数,记作 χ'Σ(G)。 确定了一类稀疏图的邻和可区别边色数,得到:若图G不含孤立边,Δ≥6且mad(G)≤5/2,则 χ'Σ(G)=Δ当且仅当G不含相邻最大度点。     

Series-Parallel图上最小权顶点覆盖3-路问题的有效算法

研究了Series-Parallel图上的顶点覆盖3-路问题,利用动态规划思想,给出一个能在多项式时间内完成的有效算法,该算法的运行时间为O（|V|）。     

不含4-圈或弦6-圈的平面图是(3,0,0)-可染的

设d₁,d₂,…,d_k是k个非负整数,若图G=(V,E)的顶点集V能被剖分成k个子集V₁,V₂,…,V_k,使得对任意的i=1,2,…,k,V_i的点导出子图G［V_i］的最大度至多为d_i,则称图G是(d₁,d₂,…,d_k)-可染的。关于平面图的染色,有以下结论:不含4-圈或弦6-圈的平面图是(3,0,0)-可染的。     

一个五阶图与星图的笛卡尔积交叉数

确定图的交叉数被证明是一个NP-完全问题,因为其难度,能够确定交叉数的具体图类非常少.M.Klecˇ等人确定了一些关于阶数不超过5的图与路、星和圈的笛卡尔积图的交叉数.本文扩展了他们的结果,确定了1个5阶图与星图的笛卡尔积图的交叉数.     

无相交三角形平面图的邻点可区别边染色

图G的k-邻点可区别边染色是指G的一个正常k-边染色满足对任意相邻顶点u和v,与u关联的边所染颜色集合和与v关联的边所染颜色集合不同。使G有k-邻点可区别边染色的k的最小值称为G的邻点可区别边色数,记作χ'_a(G)。通过运用权转移方法研究了无相交三角形平面图的邻点可区别边色数,证明了若图G为无相交三角形平面图,则χ'_a(G)≤max{Δ(G)+2,10}。     

图∪ni=1Fmi,4的优美性

给出图∪ⁿ_i=1F_{mi,4的一类非连通图, 并证明这类图是优美图, 且也是交错图.}