二连通图的最长圈

本文证明:设G为n阶2连通图,D(x)={y|y∈V(G),d(x,y)≤2},d_d~*(x)表示D(x)中所有的点的度排成的非减度序列:d_1~*,d_2~*,…,d_j~*,d_(j+1)~*,…,d_(|D(x)|)~*中当下标j=d(x)时的度。δ_0=min{d(x)|x∈V(G)},D(δ_(i-1))={x|x∈V(G),d(x)≥δ(i-1)}(i=1,2,…,k),δ_i=min{d_(d(x))~*|x∈D(δ(i-1))}(i=1,2,…,k)且δ_0<δ_1<δ_2<…<δ_(k-1)≤δ_k,则C(G)≥min{n,2δ_k}。此外也给出δ_k的算法。     

可逆上三角矩阵群的交换自同构

设G是群,φ:G→G为自同构.若对任意的x∈G,有φ(x)x=xφ(x),则称φ为G上的交换自同构.设Tn是域F上所有n×n阶可逆上三角矩阵全体按矩阵乘法构成的群,n≥3,F*为F中非零元全体组成的乘法群.证明了映射φ:Tn→Tn为Tn的交换自同构当且仅当存在群同态σi:F*→F*,1≤i≤n,使得φ(A)=(∏ni=1σi(aii))A,对A=(aij)n×n∈Tn,并且对任意的k=1,2,…,n,以及任意的a∈Imσk,方程xσ1(x)σ2(x)…σn(x)=a在F*中存在唯一解.     

Wm与Pn(n≤3)联图的点可区别边色数

设G是简单图,图G的一个k-点可区别正常边染色f是指一个从E(G)到{1,2,…,k}的映射,且满足V u,v∈V(G),u≠v,有S(u)≠S(v),其中S(u)={f(uw)|uw ∈E(G)}.数min{k|G存在k-VDPEC染色}称为图G的点可区别正常边色数,记为χs(G),研究了WmVPn(n≤3)的点可区别边染色,给出了WmVPn(n≤3)的点可区别边色数.     

树和K2,n的膨胀图的关联着色

设图G的点集V（G）=（v1,v2…,vn）,Vi是点集（i=1,2,…,n）,G的膨胀图FG的点集V（FG）=V1∪V2…∪Vn,且对x∈Vi,y∈Vj有xy∈E（FG）,当且仅当i=j或vivj∈E（G）．若对所有的i,满足｜Vi｜=t,则称其为G的一致膨胀图．证明了树的膨胀图的关联色数是最大度加1,K2,n的一致膨胀图的关联色数为最大度加2．     

2-连通图的最长圈

设 G是具有围长 g≥5 的 n 阶 2-连通简单图,P=v_1v_2…v_t 是 G的一条最长道路。若λ=min{d(u)+d(v)|u,v∈V(G),uv∈E(G)},δ~*=min{d(v_1),d(v_t)},则G的最长圈为:其中.δ= min{d(v)|v∈V(G)}。     

过特定顶点集的S-圈与S-路

证明了下面两个结论 :(1)设G是k-连通的n阶图 ,k≥ 2 ,S V(G) .若对G[S]的任意 (k 1) -独立集X ,有 k 1i=1k i- 1k si(X)>n- 1,则G中有含S的全部顶点的圈 ;(2 )设G是 (k 1) -连通的n阶图 ,k ≥ 2 ,S V(G) .若对G[S]的任意 (k 1) -独立集X ,有 k 1i=1k i - 1k si(X) >n ,则对任意的 {u ,v}≤V(G) ,G中有含S的全部顶点的 (u ,v) 路 .其中 ,G是有限无向简单图 .X为G的 (k 1) -独立集 ,Si(X) ={v∈V(G) N(v) ∩X =i} ,si(X)=si(x) ,i∈ { 0 ,1,2 ,… ,k 1} .     

Pm∨Sn的点可区别全色数

设G是简单图,f 是从V(G)∪E(G) 到{1,2,…,k}的一个映射.对每个u∈V(G),令C(u)={f(u)}∪{f(uv)|v∈V(G),uv∈E(G)}.如果f是k-正常全染色,且对任意u,v∈V(G),有C(u)≠C(v),那么称f为图G的点可区别全染色(简称为k-VDTC).数χv t(G)=min{k|G有k-VDTC}称为图G的点可区别全色数.给出m阶路Pm和n 1阶星Sn的联图的点可区别全色数.     

一类Hamilton图

若P[u,v]是2连通无爪图G的最长路,设dp(xβ,xα)=︱P[xβ,xα]︱-1(xβ相似文献   

图的强直积的2-距离染色(英文)

设G,H是阶至少为2的简单图。图G与H的强直积是指这样一个图G□×H,其顶点集合为V(G)×V(H),并且(x1,x2)(y1,y2)∈E(G□×H)当且仅当[x1y1∈E(G)且x2y2∈E(H)]或者[x1=y1且x2y2∈E(H)]或者[x2=y2且x1y1∈E(G)]。一个图G的使用了k种颜色的2-距离染色是指一个从V(G)到{1,2,…,k}的映射f,使得任意两个不同的距离最多是2的顶点染不同的颜色。对图G进行2-距离染色所需的最少的颜色数称为图G的2-距离色数,记为χ2(G)。文中将获得两个图的强直积的2-距离色数的可达到的上界和下界:Δ(G□×H)+1≤χ2(G□×H)≤χ2(G).χ2(H)。对一些特殊图,例如Pm□×Kn,Pm□×Wn,Pm□×Sn,Pm□×Fn,Pm□×Cn(n≡0(mod3)或者n=5),给出了它们的2-距离色数。     

泛圈图的一个新的充分条件

设G是一个阶为n的2－连通简单图,αv表示G中包含点v的最大独立集的点数,对任意uv不属于E,设Tuv=V\(N(u)∪N（v)),αuv=min{αu,αv}。本文证明了：如果对于任一对不相邻点u,v,｜N（u)∩N(v)｜≥min{αuv-1,｜Tuv｜},则除了一些特殊图外,对于G的任一点x和任意整数k(4≤k≤n),G包含长度为k县包含点x的圈。     

无爪图的周长

设 G为 n阶 2连通无爪图,δ=min{d(x)|x∈V(G)},δ~*=min{max(d(x),d(y))|x.y∈V(G).d(x.y)=3},则(i)c(G)≥min{n.2δ~*+4};(ii)当 δ~*≥(1/2)(n-δ-2)时 G是哈密顿图。     

关于在K1,n-free图中存在正则因子度条件的推广

图被称为K1,n-free图,如果它不含有导出子图K1,n。设G是一个具有顶点集V(G)的图,并设g和f是两个定义在V(G)的函数,使得g(x) f(x)对所有V(G)中的点x都成立。设a=max{g(x)|x∈V(G)},b=min{f(x)|x∈V(G)},并有b,a 2,n b/(a-1) 1(如果存在点v∈V(G)使得f(v)≡1(mod2),假定b n-1)。证明了:每个连通的使得∑x∈V(G)f(x)为偶数的K1,n-free图G有(g,f)-因子,如果它的最小度至少是(n-1)(a 1)b 1「b a(n-1)2(n-1) -n-1b「b a(n-1)2(n-1) 2 n-3.这个结果是K.Ota和T.Tokuda(J.GraphTheory.1996,22:59-64.)关于在K1,n-free图中存在正则因子度条件的推广。     

一个变分双曲型组的解

本文研究带Dirichlet条件的边界值问题{□u+△G(u)=f(t,x),(t,x)∈Ω≡(0,π)×(0,π), (*)u(t,x)=0, (t,x)∈aΩ,的解的存在性,这里口是波算子a2/at2-a2/ax2,GRn→R是一连续函数.设σ(口)={k2-m2,k,m∈N}记波算子口的特征值的集合,(a2G(u)/auiaui)记u∈Rn.点处的Hessian阵.假定σ((a2G(u)/auiauj))∩σ(□)=φ.再设E={u|u(t,x)=∑k,mψkm(t,x)Ckm, Ckm ∈ Rn k,m ∈ N,∑k,m(k2+m2+1)|Ckm|2 ＜+∞},Y={y|y(t,x)=∑i,k,mμikmψkm(t,x)ei,k2 - m2 ＜γi(u),μikm ∈ R,k,m ∈N,∑k,m(k2+m2+ 1)|μikm|2＜+∞,i= 1,2,……,n} Z={z|z(t,x)=∑i,k,mμikmψkm(t,x)ei,k2 -m2＞γi(u),μikm ∈ R,k,m ∈ N ,∑k,m(k2 + m2+1)|μikm|2 ＜+ ∞,i = 1,2,……,n}.对Y中的k2-m2记ξ(‖u‖0) =min‖v‖0≤‖u‖0 mink,m∈N min1≤i≤n{γi(v)-(k2- m2) ＞ 0},对Z中的k2-m2,记η(‖u‖0)=min‖v‖0≤‖u‖0 mink,m∈N min1≤i≤n{k2-m2-γi(v)＞0},这里‖·‖0记(L2(Ω))n.假设∫+∞1ξ(s)ds=∞, ∫+∞1η(s)ds=∞.在上述条件下,我们使用R.F.Manasevich的最大值最小值定理证明问题(*)的弱解u0∈(H1(Ω))n的存在性和唯一性.     

路和圈上的锥的D(2)-点可区别正常边染色

设G是顶点集合为V(G)=｛v0i|i=1,2,…,p｝的简单图,n是正整数, 称Mn(G)为G上的锥(或广义Mycielski图),如果 V(Mn(G))=｛v01,v02,…,v0p;v11,v12,…,v1p;…;vn1,vn2,…,vnp,w｝, E(Mn(G))=E(G)∪｛vijv(i+1)k|v0jv0k∈E(G), 1≤j, k≤p,i=0,1,…,n-1｝∪｛vnjw|1≤j≤p｝。 讨论了路和圈上的锥的D(2)-点可区别正常边染色,并给出了相应的色数。     

图F_m ▽S_n的边色数和邻强边色数

对图G的一个正常的k边染色法f,若 e∈E(G),e = uv,{f(uw) | uw∈E(G)}≠{f(vw) | vw∈E(G)},则称f为G 的一个k 邻强边染色法,k的最小值称为G 的邻强边色数.V(Fm Sn) = {w}∪{ui | i =1,2,…,m}∪{vij | i =1,2,…,m;j =1,2,…,n},E(Fm Sn) = {wui | i =1,2,…,m}∪{uivij | i =1,2,…,m;j =1,2,…,n}∪{uiui+1 | i =1,2,…,m-1}.　　本文得到了Fm Sn 的边色数和邻强边色数.     

星和扇上的锥的D(2)-点可区别正常边染色

设G是顶点集合为V(G)={v0i|i=1,2,…,p}的简单图,n是正整数,称Mn(G)为G上的锥(或广义Mycielski图),如果V(Mn(G))={v01,v02,…,v0p;v11,v12,…,v1p;…,vn1,vn2,…,vnp,w},E(Mn(G))=E(G)∪{vijv(i 1)k|v0jv0k∈E(G),1≤j,k≤p,i=0,1,…,n-1}∪{vnjw|1≤j≤p}.在这篇文章里,我们讨论了星和扇上的锥的D(2)-点可区别的正常边染色,并给出了相应色数.     

由轮生成的Cayley图的广义3-连通度

令S?V(G),κ_G(S)表示图G中内部不交的S-树T_1,T_2,…,T_r的最大数目r,使得对任意i,j∈{1,2,…,r}且i≠j,有V(T_i)∩V(T_j)=S,E(T_i)∩E(T_j)=?.定义κ_k(G)=min{κ_G(S)|S?V(G),且|S|=k}为图G的广义k-连通度,其中k是整数,且2≤k≤n.令Sym(n)是在{1,2,…,n}上的对称群,T是Sym(n)的对换集合.G(T)表示点集是{1,2,…,n},边集是{ij|(ij)∈T}的图.若G(T)是一个轮图,则将Cayley图Cay(Sym(n),T)简记为WG_n.主要研究由轮生成的Cayley图WG_n的广义3-连通度,并证明κ_3(WG_n)=2n-3,其中n≥4.     

Sm∨Fn的全色数

设G(V,E)是阶数至少是2的简单连通图,k是正整数,若f是从V(G)∪E(G)到{1,2,…,k}的一个映射,使得:对于任意的uv,vw∈E(G),u≠w,有f(uv)≠f(vw);且对于任意的uv∈E(G),u≠v,有f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv),则称f为G的一个k-全染色(简记成k-TC of G).而χt(G)=min{k|k-TC of G},称为G的全色数.设G和H是点边都不相交的简单图,V(G∨H)=V(G)∪V(H),E(G∨H)=E(G)∪E(H)∪{uv|u∈V(G),v∈V(H)},则称G∨H是G与H的联图.给出m 1阶星和n 1阶扇的联图的全色数.     

路和圈的距离不大于3和4的点可区别边染色

对阶数不小于3 的连通图G(V,E),设α,β为正整数,令映射f:Ef{1,2,…,α},若u,v∈V(G),1≤d(u,v)≤β,有C(u)≠C(v),则称f为G的一个α-D(β)-点可区别的边染色,简记为α-D(β)-VDPEC,对一个图进行α-D(β)-点可区别的边染色,所需的最少的颜色数称为图G 的D(β)-点可区别的边色数,记为χ′ β-vd(G),其中d(u,v) 表示u,v间的距离.研究路和圈的距离不大于3和4的点可区别边染色,得到路和圈的距离不大于3和4的点可区别的边色数.     

矩阵代数的乘法映射与反乘法映射

设P是一个域,Γn是满足{αEij|i,j=1,2,…,n,α∈P} (P)的一个乘法半群,其中Mn(P)定义P上所有n×n矩阵组成的乘法半群.证明了一个结果:若f:Γn→Mn(P)是一个保零矩阵的乘法映射,Fij(i,j=1,2,…,n)是Mn(P)中n2个矩阵,且满足FijFkl=δjkFil(i,j,k,l=1,2,…,n),则存在可逆阵S∈Mn(P),使得f(Fij)=S-1FijS,i,j=1,2,…,n.由此刻画了Γn的保迹反乘法映射.