割点数大于1的图的顶点和边PI指数

图G的顶点(边)Pardmakar-Ivan指数是到G的所有边e=uv的两个端点u和v距离不相等的总的顶点数(边数)的和。在此给出了割点数大于1的简单连通图G的顶点和边PI指数的计算公式。     

图的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-赋权乘积顶点染色的存在性.     

图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}.     

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图     

一类图中有S—闭迹的充分条件

设G是一个简单图,e=uv∈E(G),定义e的度d(e)=d(u)+d(v),其中d(u)和d(v)分别为顶点u和v的度。本文的主要结果是:设G是n≥3所无桥的简单连通图,且G不含C_3和C_4,若对任何三个相互不交的边e_0,e_1及e_2,d(e_0)+d(e_1)+d(e_1)≥n+7,则G有一个S—闭迹。     

关于Mbius梯的细分图的巧妙性

一个简单图G =(V ,E)被称为是巧妙的 (felicitous) ,若存在单射f:　V(G)→ { 0 ,1,2 ,… ,|E| }使得对所有的边e=uv∈E(G) ,由f (e) =f(x) +f(y) (mod|E| )导出的映射f :　E(G)→ { 0 ,1,2 ,… ,|E| - 1}是双射。设G是简单图 ,在G的每相邻两顶点之间都加入一个顶点后所得到的图称为G的细分图 ,文章证明了M bius梯的细分图是巧妙图     

转向细胞数为2的链状四角系统的Randi(c)指标

一个图(分子图)G的Randi(c)指标定义为图G的所有边uv上的权(d(u)d(v))·1/2之和,其中(d(u)和d(v))分别表示顶点u和v的度.Randi(c)指标是化学图论中常见且重要的一个拓扑指标.本文给出了转向细胞数为2的链状四角系统的Randi(c)指标.     

简单图中圈的长度

n阶简单图G,满足e∈E(G),e=uv,使得d(u)+d(v)≥n,在这篇文章里我们证明了图G的周长可以用图G的某些参数表示出来;并且当图G不是完全二部图时,证明了图G包含了长度为3到周长的所有圈.     

一类优美图

简单图G=(V(G),E(G)称为优美图(Graceful graph)如图存在G的一个标号f:(优美标号) V(G)—→{0,1,2……e}其中e=|E(G)|适合 (1)f是单一映射。 (2){|f(u)-f(v)||(u,y)∈E(G)}={1,2,……e}。 我们以动C_n表示一个有n个项点的圈,以C_n~1表C_n中任意两个不相邻接的顶点所得到的图,即C_n~1=C_nU{(u,v)},(u,v)E(G),我们称C_n~1是C_n的1——加边图。     

关于M(o)bius梯的细分图的巧妙性

一个简单较G＝（V，E）被称为是巧妙的（felicitous)，若存在单射f:V(G)→{0,1,2,…，|E|}使得对所有的边e=uv∈E（G），由f^*()e)=f(x) f(y)(mod|E|)导出的映射f^*:E(G)→{0,1,2…，|E|-1}是双射。设G是简单图，在G的每相邻两顶点之间都加入一个顶点后所得到的图称为G的细分图，章证明了Moebius梯的细分图是巧妙图。     

完全二部图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-全色数.     

圈的平方图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邻点全色数.     

伪-海临图的群色数

若图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.     

关于Moebius梯的细分图的κ—优美性

一个简单图G＝（V，E）是κ-优美的（κ≥1为整数），如果存在单射f:V(G)→｛0，1，2，…，|E| κ-1｝使得对所有的边uv∈E(G)，由f^*(uv)=|f(u)-f(υ)|导出的映射f^*:E(G)→｛κ,κ 1,…,|E| κ-1｝是双射，设G是简单图，在G的每相邻两顶之间都加入一个顶点后所得到的图称为G的细分图。文章证明了Moebius梯的细分图是κ－优美图。     

调和指标的极值图

图G的调和指标定义为H(G)=Σuv∈E(G)2/d(u)+d(v),其中d(u)表示G中顶点u的度。给出图的调和指标的另一种表述形式,证明了所有同阶的非空正则图的调和指标都相等,并且是同阶数图的调和指标的上界;利用一个引理,证明了固定团数和独立集阶数的Split图的调和指标的下界,并给出相应的极图。     

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

对简单图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的第一类弱全染色.给出了若干联图的第一类弱全色数.     

图的色多项式问题

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

五角链的点PI指标

图G的点PI指标指的是:取遍G中的每一条边,满足到这条边两个端点距离不相等的点的个数.为了得到五角链的点PI指标,把它的边分成三类并分别进行计算,可以得到五角链的点PI指标.利用PIv(G)=mn-∑S(e),给出二部图点PI指标的界:(n-1)n≤PIv(G)≤n.     

点泛圈偶图的一个充分条件

设G是连通偶图，（X1，X2）是其顶点的二分类，|X1|=|X2|=n，δ（G）≥t≥3。证明了若任意u,v∈Xi蕴含|N(u)∪N(v)|≥n-（t-2），i=1,2，则当t=7时G是点泛圈偶图。     

图的L(d,1)-标号的边跨度

对于给定图G顶点集上一个非负整数函数f,满足:若dG(u,v)＝1,f(u)-f(v)≥d;若 dG(u,v)＝2,f(u)-f(v)≥1.称f 为L(2,1)-标号.这是由频道分配问题抽象出来的数学模型.本文主要研究该标号问题的一个参数,即边跨度,记作βd(G)＝minf max{f(u)-f(v):u∈V(G)},即对于所有正常的L(d,1)-标号,使得相邻顶点标号之差的最大值达到最小.本文主要讨论了圈Cn、树T、 k-部完全图、正三角形网格、 正四边形网格以及弦图等图类的边跨度,并给出了确切的数值.