关于圈与完全图的笛卡儿积的测地数

对于图G内的任意两点u和v,在u和v之间的最短路称为u-v测地线.I(u,v)表示位于u-v测地线上所有点的集合,对于S V(G),I(S)表示所有I(u,v)的并,这里u,v∈S.如果I(S)=V(G),那么称S是G的测地集;并把测地集的最小基数称为G的测地数,记为g(G).文章主要研究Cn×K3的测地数.     

关于图运算的测地数

对于图G(或有向图D)内的任意两点u和v,u-v测地线是指在u和v之间(或从u到v)的最短路.I(u;v)表示位于u-v测地线上所有点的集合,对于SV(G)(或V(D)),I(S)表示所有I(u,v)的并,这里u,v∈S.G(或D)的测地数g(G)(或g(D))是使I(S)=V(G)(或I(S)=V(D))的点集S的最小基数.G的下测地数g-(G)=min狖g(D):D是G的定向图狚,G的上测地数g+(G)=max狖g(D):D是G的定向图狚.对于两个图G和H,u∈V(G)和v∈V(H),在u和v之间加一条边,然后再收缩这条边uv所得的图,记为GuHv.本文主要研究图GuHv的测地数和上(下)测地数.     

含有割点的图的测地集

对于图G内的任意两点u和v,u-v测地线是指在u和v之间的最短路．I（u，v）表示位于一条u-v测地线上所有点的集合，对于S包含V（G），I（S）表示所有，（u，v）的并。这里u，u∈S．G的测地数g（G）是使I（S）=V（G）的最小点集S的基数．图的每个最小测地集都不包括它的割点，如果图G是一个有n≥3个顶点，k≥1个割点的块图．那么g（G）=n-k．树T有n≥2个顶点，l片叶子。如果将树T的所有点ui用图Hi来代替。用Hi∨Hj来代替树T的所有边uivj∈E（T），将得到的新图定义为Tn（H）。有g（Ta（Kd））=ld和g（Tm（Cd））≤min{[d/2]l。2（n-l）}/．     

星图S5及5个六阶图与路的笛卡儿积图的交叉数

两个图G1和G2的笛卡尔积图G1×G2是这样一个图:V(G1×G2)=V(G1)×V(G2),E(G1×G2)={(u1,u2)(v1,v2)|u1=v1,且u2、v2∈E(G2)或者u2=v2,且u1、v1∈E(G1)}.星图Sm表示完全偶图K1,m,Pn表示长为n的路.这里确定了星图S5及5个六阶图与路的笛卡儿积图的交叉数.     

图的强彩虹连通数

如果图G的任意两个顶点由一条路P连接,其中路P的每一条边着不同的颜色,则称图G为彩虹连通图.对图G的任意两个顶点u和v,G的彩虹u-v测地线是一条长为d(u,v)的彩虹路,其中d(u,v)表示最短的u-v路的长度.图G称为强彩虹连通的如果对G的任意两点u和v间都存在一条彩虹u-v测地线.图G的强彩虹连通数是指使得图G是强彩虹连通而用的最少颜色的数目,用src(G)表示.该文首先给出了一个含边不交的k-圈图的一个强彩虹连通数的上界.接着给出了这个上界取等的充分条件.     

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的联图的点可区别全色数.     

关于Cm·Fn的邻点可区别全染色

Cm·Fn表示m个n 1阶扇Fn的扇心连成圈.设Cm=u1u2…umu1,V(Cm·Fn)=V(Cm)∪mi=1{vij|j=1,2,…,n},E(Cm·Fn)=E(Cm)∪mi=1{uivij|j=1,2,…,n}∪mi=1{vi(j 1)vij|j=1,2,…,n-1}.得到了Cm·Fn的邻点可区别全色数.     

路和圈的联的Wiener指数

G=(V,E)是一个简单连通图,其中V和E分别为G的顶点集和边集.一个图G的Wiener指数W(G)是指图G中所有顶点对之间的距离之和,即W(G)=∑{u,v}■G dG(u,v).文章给出了Pn∨Pm和Pn∨Cm的Wiener指数.     

合成图C_n[H]的星全染色

简单图G和H的合成图是指具有顶点集V(G)×V(H)的简单图G[H],它的顶点(u,v)和另一个顶点(u′,v′)相邻当且仅当或者uu′∈E(G),或者u=u′且vv′∈E(H).论文研究了n阶简单图G与m阶简单图H的合成图的星全染色,其中G为n阶圈,得到了圈与某些特殊图的合成图的星全色数.     

关于图的哈密尔顿性的一些新的结果

关于哈密尔顿图和哈密尔顿连通的两个基本结果是Ore给出的:设G是一个n(n≥3)阶图,如果对于G的任意一对不相邻顶点u,v,有d(u) d(v)≥n或n 1,则G是哈密尔顿图或哈密尔顿连通的.设G是一个图,对于任意u∈V(G),令N(u)表示u的邻点集;对于任意U∈V(G),令N(U)=∪u∈UN(u).本文利用插点方法,给出了关于k或(k 1)-连通图(k≥2)G是哈密尔顿的,哈密尔顿连通的或1-哈密尔顿的统一证明.其充分条件是关于|N(S)| |N(T)|与n(S ∪T)的不等式,这里S,T是图G的任意两个不交的独立集,并且|S|=s,|T|=1,S∪T也是一个独立集,这里n(S∪T)=|{v∈V(G):dist(v,S∪T)≤2}|.     

路的笛卡尔积图的Wiener指数

G=(V,E)是一个简单连通图,其中V和E分别为G的顶点集和边集.一个图G的Wiener指数W(G)是指图G中所有顶点对之间的距离之和,即W(G)=∑{u,v}GdG(u,v).给出了Pm×Pn的Wiener指数.     

几类图的均匀邻点可区别全染色

 邻点可区别全染色是在正常全染色的定义下,使得任两相邻顶点的色集不同。设G（V,E）为一个简单图,f为G的一个k-邻点可区别全染色,若f满足||Vi∪Ei|－|Vj∪Ej||≤1（i≠j）,其中,Vi∪Ei={v|f（v）=i}∪{e|f（e）=i},记C（i）=Vi∪Ei,则称f为G的k-均匀邻点可区别全染色,简记为k-EAVDTC,并称χeat（G）=min{k|G存在k－均匀邻点可区别全染色}为G的均匀邻点可区别全染色数。本文给出了路、圈、风车图K t 3、图Dm,4和齿轮图■n的均匀邻点可区别全染色,以及它们的均匀邻点可区别全色数的确切值。     

Cartesian积图的最大拉普拉斯特征值

设G=(V(G)),E(G)),H=(V(H),E(H))是两个简单的连通图,定义与的Cartesian积G×H图是:其顶点集为V(G×H)=V(G)×V(H),其中任何两个顶点(u,u’),(v,v’),相邻当且仅当u=v且u’,v’在H中相邻;或u’=v’且u,v在G中相邻,这里u,v∈V(G),u’,v’∈V(H).本文研究两个图的Cartesian图的拉普拉斯矩阵的最大特征值,得到如下结论:设简单图G具有n顶点m条边,图H具有P个顶点q条边,那么G和H的Cartesian积图G×H的拉普拉斯最大特征值p(L(G×H))≤2m/n[1+(n-1)(((n3/4m2)-(1/n-1))～(1/2))]+((2p-1)～(1/2))+1.     

W_m与P_n（n≤3）联图的点可区别边色数

设G是简单图,图G的一个k-点可区别正常边染色f是指一个从E（G）到{1,2,…,k}的映射,且满足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）,研究了Wm∨Pn（n≤3）的点可区别边染色,给出了Wm∨Pn（n≤3）的点可区别边色数.     

K1×mCn的k-边优美指标集

设G=(V,E)是一个p点q边图.对于非负整数k,若存在双射f:E→{k,k+1,…,k+q-1},使得其导出映射f+:V→Zp,f+(u)≡∑(u,v)∈Ef(u,v)modp也是一个双射,则称此图G是k-边优美的.称EGI(G)={k:G是k-边优美的}是G的边优美指标集.在此彻底解决了图K1×mCn(mn≡0mod 2)的边优美指标集.     

Cm×Kn的邻点可区别全染色

设G（V，E）是阶数至少为2的简单连通图，k是正整数，V∪E到{1，2，3，…，k）的映射f满足：对任意uυ，υw∈E（G），u≠w，有f（uv）≠f（υw）；对任意uυ∈E（G），有，（u）≠，（υ），f（u）≠f（uυ），f（υ）≠f（uυ）；那么称f为G的k-正常全染色，若，还满足对任意uυ∈E（G），有C（u）≠C（υ），其中C（u）={（u））∪{f（uυ）｜uυ∈E（G），υ∈V（G）），那么称，为G的k-邻点可区别的全染色（简记为k-AVDTC），称min{k｜G有k-邻点可区别的全染色）为G的邻点可区别的全色数，记作xat（G）．本文得到了圈Cm和完全图Kn的笛卡尔积图Cm×Kn邻点可区别的全色数．     

没有某些圈的平面图的3可选择性

设G=(V,E)是一个图,对G的每一点v给一颜色集L(v).G称为L列表可染的,如果存在G的点染色f满足:f(u)≠f(v),(u,v)∈E(G),且f(u)∈L(u),u∈V(G).G称为k可选择的,对于任何列表L(v)(这里每一个L(v)恰有k个元素)G都是L列表可染的.本文研究了没有某些圈的平面图的可选择性,证明了没有4,5,7,10圈的平面图是3可选择的.     

Halin图的集染色

对于非平凡连通图G,G的k集染色是指映射c：V（G）→Nk,对任意顶点v∈V（G）,定义邻色集cN（v）={c（u）｜u∈N（v）},若对uv∈E（G）有cN（u）≠cN（v）,则称c为G的一个k集染色.满足上述条件的最小k值称为G的集色数,记为χs（G）.为了更快更有效地给Halin图着色,采用集染色的着色方法,证明了当p≥4时,Halin图G（Cp,Tq）的集色数是3,并且还证明了对任意的Halin图G（Cp,Tq）,有p＋1≤q≤2p-2成立.