笛卡尔积图Tn×Cm的交叉数

两个图G1和G2的笛卡尔积图G1×G2定义为如下的图:V(G1×G2)=V(G1)×V(G2),E(G1×G2)={(u1,u2)(v1,v2)|u1=v1且u2v2∈E(G2),或者u2=v2且u1v1∈E(G1).图的交叉数是图论中的一个重要拓扑参数,而确定图的交叉数是一个完全NP-问题.本文确定了若干树Tn(n≤4)与圈Cm的笛卡尔积图的交叉数.     

笛卡儿积图P2n×Pm与P2n×Cm的gnd-染色

设简单图G和图H的顶点集分别为V(G)={u1,u2,…,um}和V(H)={v1,v2,…,vn}.所谓G和H的Cartesian积G×H是指这样的一个图,其顶点集和边集分别为V(G×H)={wij|i=1,2,…,m,j=1,2,…,n},E(G×H)={wijwrs|i=r,vjvs∈E(H)或j=s,uiur∈E(G)}.文章讨论了笛卡儿积图P2n×Pm和P2n×Cm的gnd-染色,并给出了相应色数.     

关于PnVPn和SnVSn的Mycielski图的边染色

对图G（V,E）,μ（G）称为G的Mycielski图,V（μ（G））=y（C）U{v＇｜v∈V（G））U{w},且w∈V（G）,而E（μ（G））=E（G）U{uv＇｜u∈V（G）v’∈V’,且uv∈E（G））U{wv＇tv’∈V’）其中w∈V（G）,V’={v＇｜v∈V（G））．     

圈的平方图的Smarandachely邻点全色数

对简单图G（V,E）f,是从V（G）∪E（G）到{1,2,A,k}的映射,k是自然数,若,满足（1）u,v∈E（G）,u≠,f（u）≠f（v）;（2）Vuv,uw∈E（G）,v≠w,f（uv）≠f（uw）;（3）uv∈E（G）,＼G（u）＼C（v）＼≥1并且IG（v）＼C（u）1≥1;则称f是G的Smarandachely邻点全染色．本文给出了圈的平方图的的Smarandachely邻点全色数．     

关于几类图的Fractional全控制数

设G=（V,E）是一个无孤立点的图,一个实值函数f：V→[0,1]满足∑v∈N（u）f（v）≥1对一切u∈V（G）都成立,则称f为图G的一个Fractional全控制函数。图的Fractional全控制数定义为γ0f（）G=min{f（V）｜f为图G的Fractional全控制函数},文章中研究了图的Fractional全控制问题,主要给出了关于联图的Fractional全控制数的一个上界,由此确定了几类特殊图的Fractional全控制数,并推广了部分已知结果。     

完全二部图K6,n当n较小时的点可区别IE-全染色

设G是简单图,图G的一个k-点可区别IE-全染色(简记为k-VDIET染色),f是指一个从V(G)∪E(G)到{1,2,…,k}的映射,且满足:uv∈E(G),有f(u)≠f(v);u,v∈V(G),u≠v,有C(u)≠C(v),其中C(u)={f(u)}∪{f(uv)|uv∈E(G)}.数min{k|G有一个k-VDIET染色}称为图G的点可区别IE-全色数,记为χviet(G).本文给出了完全二部图K6,n(7≤n≤243)的点可区别IE-全色数.     

链状四角系统的Randic指数

设G=（V,E）是一个图,其中顶点集V={v1,v2,…,vn}．G的Randid指数为：X（G）=∑vjvj∈E（G）1/√d（vi）d（vj）,其中d（v）表示顶点v的度．Randic指数是化学图论中常见且重要的一个拓扑指数．给出直链四角系统、锯齿链四角系统和转向细胞个数为1的链状四角系统的Randid指数．     

图的2-赋权乘积顶点染色

图G=(V,E)的k-赋权w是对图的每条边e∈E安排一个权值w(e)∈{1,2,…,k}.由边权导出图G的一个乘积顶点染色c,使得对图的每一个顶点v,c(v)=∏v∈e w(e)且对任意的边e=uv∈E,都有c(u)≠c(v).本文研究了Kn-e,Pm×Pn(m,n≥2)和Pm×Cn(m≥2)2-赋权乘积顶点染色的存在性.     

图的谱半径的下界

设G=（V,E）是n阶简单图,di是图G的顶点vi（i=1,2,……,n）的度且d1≥d2≥…≥dn,Ni是图G的顶点vi的一个邻集,λ1是图G的邻接谱半径．本文证明了λ1≥√d1,等号成立当且仅当图G同构于K1,n-1。最后证明了当v1v2≠E时,λ1≥√d2＋｜N1∩N2;当v1v2∈E时,λ1≥√d2-1＋｜N1∩N2｜.     

关于双图的群染色（英文）

若图G=（V,E）,给定方向为D,A表示一个非平凡的阿贝尔群,F（G,A）表示映射f：E（G）→A的集合.若对任意f∈F（G,A）存在映射c：V（G）→A,使得G中的每一条有向边e=uv∈E（G）（方向是u→v）满足c（u）-c（v）≠f（e）,这时说图G是A-可染的.使得图G在方向D下是A-可染的,A的最小阶数为图G的群色数,记为χg（G）.主要是在分析了一些双图的特性的基础上讨论了它们的群色数.对于任意阶路的双图可得出其群色数都是3,还证明了圈的双图的群色数不超过5以及得到其它一些双图的群色数的上界.     

Petersen图的关联图的Hamilton-性

对图G（V,E）,定义图I（G）为如下图：V（I（G））＝｛（ve)|v∈V（G）,e∈E（G）且v与e关联｝,E（I（G））＝｛（ue,vf）｜u＝v或e＝f或uv＝e或uv＝f｝称I（G）为G的关联图,其中（ue,vf）表示关联图I（G）的以ue和vf为端点的边、本文证明了Petersen图的关联图是Hamilton图     

圈的平方图Smarandachely邻点全色数

对简单图G(V,E)f,是从V(G)∪E(G)到{1,2,Λ,k}的映射,k是自然数,若f满足(1)u,v∈E(G),u≠,f(u)≠f(v);(2)uv,uw∈E(G),v≠w,f(uv)≠f(uw);(3)uv∈E(G),\C(u)\C(v)\≥1并且|C(v)\C(u)|≥1;则称f是G的Smarandachely邻点全染色.本文给出了圈的平方图的的Smarandachely邻点全色数.     

树和乘积图的圆L（j,k）-标号数（英文）

设j,k和m是3个正整数.给定一个图G.设f：V（G）→{0,1,…,m-1}是一个映射.如果对图G的任意一对相邻顶点u和v都有f（u）-f（v）m≥j,对任意一对距离为二的顶点都有f（u）-f（v）m≥k,其中a-bm=min{a-b,m-a-b},则称f是图G的一个圆m-L（j,k）-标号.使得图G有圆m-L（j,k）-标号的最小的正整数m称为图G的圆L（j,k）-标号数,记为σj,k（G）.对任意2个满足j≤k的正整数,确定了树以及2个完全图的笛卡尔乘积图和直积图的圆L（j,k）-标号数.     

图Pm+Pn的Smarandachely邻点边色数

对简单图G(V.E),f是从E(G)到{1,2,…,k}(k是自然数)的映射,若f满足:(1)()uv,uw∈E(G),v≠w,f(uv)≠f(uww);(2)()uv∈E(G).|C(u)＼C(v)|≥1,并且|C(v)＼C(u)|≥1;则称f是G的Smarandachely邻点边染色.文章给出了m(m=2,3,4)阶路与n阶路的联图的smarandachely邻点边色数.其中C(u)={f(uv)|uv∈E(G)且u≠v}.     

关于P_n∨P_n和S_n∨S_n的Mycielski图的边染色

对图G(V,E),μ(G)称为G的Mycielski图,V(μ(G))=V(G)∪{v′|v∈V(G)}∪{w},且w■V(G),而E(μ(G))=E(G)∪{uv′|u∈V(G)v′∈V′,且uv∈E(G)}∪{wv′|v′∈V′}其中w■V(G),V′={v′|v∈V(G)}.     

C_n~2图的符号控制数

设图G=G(V,E),令函数f:V→{-1,1},f的权w(f)=∑v∈Vf[v],对v∈V,定义f[v]=∑u∈N[v]f(u),这里N[v]表示V中顶点v及其邻点的集合。图G的符号控制函数为f:V→{-1,1}满足对所有的v∈V有f[v]≥1,图G的符号控制数γs(G)就是图G上符号控制数的最小权,称其f为图G的γs-函数。研究了C2n图,通过给出它的一个γs-函数得到了其符号控制数。     

关于若干联图的第一类弱全色数

对简单图G(V,E),f是从V(G)u E(G)到{1,2,…, k}的映射,K是自然数,若,满足(1) uv∈E(G),u≠v,f(u)≠f(v);(2) uv,uw∈E(G),v≠w,f(uv)≠f(uw);则称/是G的第一类弱全染色.给出了若干联图的第一类弱全色数.     

广义轮图的F-控制

设G=(V,E)是一个图,一个实值函数f:V→[0,1]满足∑v∈N[u]f(v)≥1对一切u∈V(G)都成立,则称f为图G的一个Fractional控制函数。图G的Fractional控制数定义为γf(G)=min∑v∈V(G)f(v)f为图G的Fractional{}控制函数。本文主要解决了一类特殊图,即广义轮图的Fractional控制数。     

伪-海临图的群色数

若图G=(V,E),给定方向为D,A表示一个非平凡的且单位元为0的阿贝尔群,F(G,A)表示映射f:E(G)→A的集合.若对任意f∈F(G,A)存在映射c:V(G)→A,使得G中的每一条有向边e=uv∈E(G)(方向是u→v)满足c(u)-c(v)≠f(e),这时说图G是A-可染的.使得图G在方向D下是A-可染的,A的最小阶数为图G的群色数,记为χg(G).本文给出了伪-海临图的群色数不超过4.     

图的色多项式问题

定义1 设图G为含有P个顶点的标定图,对其进行X—正常染色的方法数是X的一个函数,可表示成X的一个多项式,称为图G的色多项式,记为f(G,X)。 引理1 给定图G,设u、v∈V(G),e=(u,v)∈E(G)