一类Y~(SG)(γλ,n)∪βS_n~G形图簇的伴随分解及其补图的色等价性

设G是m阶连同图,我们用S_n~G(n=km+1)表示把kG的每个分支的d_i度点分别与星图S_k+1的k个1度点重迭后得到的图,Y~(SG)(r_1n,n)表示把r_1S_n~G中每个分支的k度点依次与图的k度点邻接后得到的图,Y~(SG)(r_2λ_1,n)表示把τ_2Y~(SG)(τ_1n,n)中每个分支的r_1+k度点依次与图S_n~G的k度点邻接后得到的图,若k≥3,用Y~(sG)(r_kλ__(k-1),n)表示把τ_kY~(sG)(r_(k-1)λ_(k-2),n)中每个分支的τ_(k-1)+k度顶点依次与图S_n~G的k度点邻接后得到的图,这里λ_k=r_kλ_(k-1)+n.运用图的伴随多项式的性质,证明了一类新的图簇Y~(sG)(r_kλ__(k-1),n)∪β_kS_n~G的伴随多项式的因式分解定理,进而得到了这类图的补图的色等价图.     

证明图ρ_n~G(i)∪G等的伴随分解及色等价性

设P_m和C_m分别表示具有m个顶点的路和圈,G是任意的r阶连通图,设m是偶数,把路P_(m-1)的标号为偶数的2~(-1)m个顶点分别与2~(-1)mG每个分支的第i个顶点V_i重迭后的图记为ρ_((m-1)+2~(-1)mr)~G(i),令n=(2m+1)+(m+1)r,把图kρ_n~G(i)的每个分支的一个d(v_i)+1度顶点分别与S_(k+1)的k个1度点重迭后所得到的图记为Y_(kn+1)~(PG),运用图的伴随多项式的性质,首先给出了一类图簇ρ_n~G(i)和Y_(kn+1)~(PG)的伴随多项式.在讨论上述图的伴随多项式的基础上,证明了图ρ_n~G(i)∪G、Y_(kn+1)~(PG)∪(k-1)K_1和Y_(kn+1)~(PG)∪(k-1)K_1∪(k-1)G的伴随多项式的因式分解定理,进而证明了这些图类的补图的色等价性.     

Φ~S-型图簇的伴随分解及其色性分析

运用图的伴随多项式的性质,讨论了图簇ΦS((kn+1)σ,nσ)∪2kSσ的伴随多项式的因式分解定理,进而证明了它们的补图的色等价性.     

图簇Y_(λ_kδ)∪β_kS_δ~*的伴随分解及其补图的色等价性

设P_n是具有n个顶点的路,令δ=rn+1,我们S_δ~*表示把rP_(n+1)的每个分支的一个1度点重迭在一起得到的图.用Y_(λ_1δ)~(S*)表示把r_1S_δ~*中每个分支的r度顶点与S_δ~*的r度顶点依次邻接后得到的图,Y_(λ_2δ)~(S*)表示把用r_2Y_(λ_1δ)~(S*)中每个分支的r+r1度顶点与S_δ~*的r度顶点依次邻接后得到的图,一般地,Y_(λ_kδ)~(S*)表示把用r_kY_(λ_(k-1)δ)~(S*)中每个分支的r+r_k-1度顶点与S_δ~*的r度顶点依次邻接后得到的图,运用图的伴随多项式的性质,证明了图Y_(λ_kδ)~(S*)∪β_kS_δ~*的伴随多项式的因式分解定理,进而得到了这类图的补图的色等价性.     

图簇YS*λκδUβκS*δ的伴随分解及其补图的色等价性

设Pn是具有n个顶点的路,令δ=rn+1,我们用S*δ表示把γPn1的每个分支的一个1度点重迭在一起得到的图.用YS*λ1δ表示把γ1S*δ中每个分支的r度顶点与S*δ的γ度顶点依次邻接后得到的图,YS*λ2δ表示把用γ2YS*λ2δ中每个分支的γ+γ1度顶点与S*δ的γ度顶点依次邻接后得到的图,一般地,YS*λ2δ表示把用γκYS*λ-1δ中每个分支的γ+γk-1度顶点与S*δ的r度顶点依次邻接后得到的图,运用图的伴随多项式的性质,证明了图YS*λ2δ∪βκS*δ的伴随多项式的因式分解定理,进而得到了这类图的补图的色等价性.     

若干完全三部图的色唯一性

用P(G,λ)表示图G的色多项式.若对任意图H,当P(H,λ)=P(G,λ)时都有H和G同构,则称图G是色唯一的.给出了以下结果:m≥2且k≥0时,完全三部图K(m,m,m+k)是色唯一的;m≥2且m+1>k≥0时,完全三部图K(m,m+1,m+k)是色唯一的.     

非连通图G_1uG_2及G_1uG_2uK_2的优美性

将k-优美图的概念进行了推广,引入了k～l 优美图及标号间距的概念,并以此为基础, 分别推出了一般情形下判定非连通图G_1 ∪G_2及G_1 ∪G_2 ∪K_2是优美图的两个充分条件;同时得出了图(C_3 ∨(?)_n)∪St(m)∪K_2是优美图,其中k、l 为自然数,l相似文献   

图的伴随多项式基于挖补定理的因式分解及其色性分析

通过研究H_t~Γ及H_t~L类图簇的伴随多项式的因式分解,证明了两类图的补图的色等价图的结构性质和非色唯一性.     

S~(GS*)类图簇的伴随多项式的因式分解及其色性

通过研究SGS*类图簇的伴随多项式的因式分解,证明了这类图簇的补图的色等价图的结构特征.     

一类完全三部图的色唯一性

用P(G,λ)表示简单图G的色多项式.设G是一个给定的简单图,若对任意简单图H,当P(H,λ)=P(G,λ)时都有H和G同构(记为H≌G),则称图G是色唯一的.本文证明了以下结果:设n,k,△都为非负整数,其中k≥0,△∈{4,5},若n≥1/3k~2+1/3△~2-1/3k△-1/3k-1/3△+4/3,则完全三部图K(n,n+△,n+k)是色唯一的.同时还给出了一个猜想.     

小直径图的导出匹配覆盖

设G是一个图,而M1,M2,…,Mk是G的k个导出匹配.称{M1,M2,…,Mk}是图G的一个k-导出匹配覆盖,若V(M1)∪V(M2)∪…∪V(Mk)=V(G).k-导出匹配覆盖问题是指对任一个给定的图G是否存在一个k-导出匹配覆盖.这篇文章证明了:直径为6的图的2-导出匹配覆盖问题和直径为2的图的3-导出匹配覆盖问题是NP-完备的,直径为2的图的2-导出匹配覆盖问题多项式可解.     

最大亏格、点度和围长

用g(G)和δ(G)分别表示一个图G的围长和顶点最小度. ζ(G)为图G的Betii亏数,主要证明了以下2个结果1)设G为k-边连通简单图,若对G中任意圈C,存在点x∈C满足dG(x)＞|V(G)|/(k-1)2+2)+k-g(G)+2,k=1,2,3,则G是上可嵌入的.且不等式的下界是最好的;2)设G为k-边连通简单图,则ζ(G)≤{max{1,m},k=1,max{1,1/(k-1)m -1}K=2,3 其中m= |V(G)|g(G)-6/g(G)2+(δ(G)-2)g(G)-4'且不等式的上界是可达的.进而得到了最大亏格一个比较好的下界.     

区间上单峰扩张自映射周期轨道的超旋转对

设f是区间I=[0,1]上的单峰扩张自映射, k ∈N,m≥2,λm,k是方程x(k-1)m(xm- 1)Q(x,m 1) (x(k-1)m-1)Q(x,m)=0在(1, ∞)上的唯一实根,其中Q(x,m)=(xm- 2xm-1 1).本文证明:若f的扩张常数λ≥λm,k,则f有超旋转对为(k,km 1)的周期轨道. 此外,还指出,当1<λ<λm,k时,在区间上存在单峰扩张自映射具有扩张常数λ却无超旋转对为(k,km 1)的周期轨道.     

区间上单峰扩张自映射周期轨道的超旋转对

设f是区间I=[0,1]上的单峰扩张自映射,k∈N,m≥2,λm,k是方程x(k-1)m(xm-1)Q(x,m+1)+(x(k-1)m-1)Q(x,m)=0在(1,+∞)上的唯一实根,其中Q(x,m)=(xm-2xm-1+1).本文证明若f的扩张常数λ≥λm,k,则f有超旋转对为(k,km+1)的周期轨道.此外,还指出,当1＜λ＜λm,k时,在区间上存在单峰扩张自映射具有扩张常数λ却无超旋转对为(k,km+1)的周期轨道.     

关于K4(2,3,3,δ,ε,η)色性问题的一个研究

证明：在K4-同胚图K4(2，3，3，δ，ε，η)图簇中，任何两个不同构的图都不是色等价的，这一结论从色多项式的角度刻划了K4同胚图K4(2，3，3，δ，ε，η)的结构特征，为进一步研究K4-同胚图的色唯一性奠定了基础。     

图匹配多项式的因式分解及其应用

通过讨论几类图簇匹配多项式的因式分解,给出了两类图簇匹配等价图的结构性质,从而得到几类新的非匹配唯一图.     

超图与图公平划分的l-元组

令S为一个图或超图的某顶点子集,则e(S)表示该图中端点全部在S内的边数. Fan和Hou(2017)证明了每个最大度为?的m阶图G都存在一个k部划分(V_1, V_2,..., V_k),使得对于任意1≤i j≤k,都成立e(V_i∪V_j)min≤{4/k~2×m+4?/k,m/k-1}+o(m~(7/8)).令H表示最大度为?的m阶r-一致超图,本文证明H存在一个k部划分(V_1, V_2,..., V_k),对于任意1≤i j≤k,满足e(V_i∪V_j)≤r-1/k-1×m+o(m);也证明当?=o(m)时, H存在一个k部划分(V_1, V_2,..., V_k),使得对于任意l∈[k-1]和每个l元组(V_(j1),..., V_(jl)),有e(V_(j1)∪···∪V_(jl))≤l~r/k~r/m+o(m).     

完全多部图K_(1*r,3*(k-2))的m数

如果对一个图G的每个顶点v,任给一个k-列表L(v),使得G要么没有正常列表染色,要么至少有两种正常列表染色,则称图G具有M(k)性质.定义图G的m数为使得图G具有M(k)性质的最小整数k,记为m(G).已有研究表明,当k=3,4时,图K_(1*r,3*(k-2))具有M(k)性质,且当r≥2时,m(K_(1*r,3*(k-2)))=k.本文将上述结论推广到每一个k,证明了对任意r∈N~+,k≥3,图K_(1*r,3*(k-2))具有M(k)性质,且当k≥4,r≥(k-2)时,m(K_(1*r,3*(k-2)))=k.此外,得到图K_(1,3,3,3)的m数为4,该图是图K_(1*r,3*(k-2))中r=1,k=5时的特殊情况,同时也是现有研究中尚未解决的一个问题.     

具有色多项式∑n＋2／k[k n＋2—k]（λ）k＋1的图

本文讨论了色项式为∑/k≤n 2(n 2)/k[k n 2-k](λ）k 1的图的结构,给出了具有这种色多项式的全部色等价图。     

ED(i)形图簇的伴随多项式的因式分解及色性分析

令Dm表示三阶完全圈K3的一个顶点与路Pm-2的一个1度点重迭后得到的图；ψD^(i)(k,m），表示把Dm的第i个顶点（第1个顶点是1度点）与星图Sk 1的k度点重迭后得到的图；Erm r-1^D(i)表示把rDm中一个分支的第i个顶点与Sr的r-1度点重迭，同时把其余r-1个分支的第i个顶点分别与Sr的r-1个1度点都依次连一条边后得到的图。我们证明了对于1≤i≤m,r≥2，科簇Erm r-1^D(i) ∪(r-1)K1与Dm∪(r-2)ψD^(i)(1,m)∪ψD^(i)(r,m)两的补图是色等价的。