一类剪刀积图H(○)G的亏格

设H和G为连通图,H和G的剪刀积图H(○)G定义为:V(H(○)G)=V(H)×V(G),E(H(○)G)={(u,v) (s,t)| uv∈E(H),st∈E(G)}.利用电压图及其覆盖图的嵌入理论,本文研究了当第一个因子H为一条路,第二个因子G为Cayley图时,这类剪刀积图H(○)G的亏格.本文的结果可视为目前在研究这类图的亏格上的一个补充,且较大程度上推广相关文献的主要结果.     

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阶扇的联图的全色数.     

图的强直积的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-距离色数。     

一类字典积Cn[H]的星全染色

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

联树模型在亏格等式证明中的应用

应用联树模型,把图浸入平面,获得这个图的关联曲面,从而获得这个图的嵌入曲面的亏格.应用这个方法,我们证明了2个著名的亏格等式.第1如果e是图G的一条割边,G-e有2个分支G1,G2,那么,g(G1) g(G2)=g(G).其中g(G)表示图G的亏格.第2用H*vK表示图H与K在点v处的结合,即V(H)∩V(K)=v,E(H)∩E(K)=φ.γ(G)表示图G的最小可定向亏格.那么,γ(H*vK)=γ(H) γ(K).     

与任意图(m,r)-正交的(g,f)-因子分解

设G是一个图,用V(G)和E(G)分别表示它的顶点集和边集,并设g(x)和f(x)分别是定义在V(G)上的非负整数值函数,且对每个x∈V(G)有g(x)相似文献   

具有与星正交的(g,f)-因子分解的子图

设 G是一个图 ,用 V(G)和 E(G)表示它的顶点集和边集 ,并设 g(x)和 f (x)是定义在 V(G)上的两个整数值函数 ,且对任意的 x∈ V(G)有 0≤ g(x) 相似文献   

笛卡尔积图K2,5×Pn的交叉数

两个图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)﹜.确定了笛卡尔积图K(2,5)×P(n)的交叉数为8n.     

与任意图2-正交的(g,f)-因子分解

设G是一个图，用V(G）和E(G）表示它的顶点集和边集，并设g(x）和f(x）是定义在V(G）上的两个整数值函数，且对每个x∈V(G），有4≤g(x)≤f(x)，则图G的一个支撑子图F称为G的一个（g，f）-因子，如果对每个x∈V(G)，有g(x)≤dF(x)≤f(x)。图G的（g，f）-因子分解是指E(G）能划分成边不交的（g，f）-因子，设F={F1,F2,…,Fm}和H分别是图G的因子分解和子图，若对所有1≤i≤m有|E(H)∩E(Fi）|=2，则称F和H2-正交。本文证明：若G是一个（mg m-1，mf-m 1）-图，H是G中任一有2m条边的子图，则G有一个（g，f）-因子分解与H2-正交。     

若干图的Mycielskian图的边色数

对图G(V,E),μ(G)称为G的Mycielskian图,若V(μ(G))=V(G)∪{v′|v∈V(G)}∪{w}且w V(G),而E(μ(G))=E(G)∪{uv′|uv∈E(G)}∪{wv′}.研究了路、圈、扇、轮图的Mycielskian图的边色数.     

积图的点PI指标

图G的点PI指标PIv(G)=∑e∈E(G)v更近的点的个数。两图G和H的积图G∨H的点集是V(G)×V(H);点(a,b)和(c,d)是相邻的当且仅当a和c或b和d分别在G和H中是相邻的。文章给出了积图G∨H的点PI指标的表达式。     

满足xyz=--+的变换图Gxyz

图G的变换图G--+以V(G)∪E(G)为其顶点集,对任意的α,β∈V(G)∪E(G),α和β在图G--+中邻接的条件如下:(ⅰ)α,β∈V(G), 且α和β在G中不相邻,(ⅱ) α,β∈E(G), 且α和β在G中不相邻,(ⅲ) α∈V(G),β∈E(G), 且它们在G中相关. 本文主要证明除了12个图外,G--+都不是可平面图, 以及对于图G, G--+ ≌Pn--+当且仅当G≌Pn.     

每点都与3度点相邻的最大临界3棱连通图的结构

没G=(V,E)是3棱连通图,若对每个x∈V(G),G-x 不是3棱连通的,则称G 为临界3棱连通图.p 阶临界3棱连通图的全体记为(?)_3(p),G∈(?)_3(p)称为最大的,如果不存在H∈(?)_3(p),使|E(H)|>|E(G)|.本文给出每个点都与3度点相邻的p 阶最大临界3棱连通图的结构.     

关于边控制集的一些结论

令G＝（V，E）是一个图，M是边集E（G）的子集，如果有e∈E（G）／M，e至少与M中一条边相连，则称M为图G的边控制集，进一步，若M是匹配，则称M为图G独立边控制集，本文给出关于边控制集的一些结论。（1）设图H，S是两中连勇图，且H,S∈ж，γe(S)=1,M和M′＝｛uv｝分别是图H和S的唯一最小边控制集，其中S是图1中的（G1，G2，G3，G4）四个图之一，对任何点x∈V（S）＝｛u,v｝,y∈V(H)-V(M),令G＝H（y=s)S，则G∈ж，（2）如果连通图G≠K2，G∈ж，γe(G)=k,则存在G的两个连通于图H，S和某两个正整数l,m使H∈ж，S∈ж，且γe(H)=k-l,γe(S)=l,G≌H（yi=xi)S,其中l≤i≤m.     

变换图G++-的连通度

本文所研究的图G的变换图G++-是以V(G)∪E(G)作为顶点集的图,它的两个顶点u与v被一条边连接当且仅当下列情形之一成立:(ⅰ)如果u,v∈V(G),那么它们在G中邻接.(ⅱ)如果u,v∈E(G),那么它们在G中邻接.(ⅲ)如果u与v一个属于V(G)而另一个属于E(G),那么它们在G中不关联.文章给出了变换图G++-的连通度的一个下限.     

Mycielski图的P4分解

给定图G=(V,E),G的Mycielski图μ(G)被定义为一个新图:V(μ(G))=V∪V'∪{w},其中V'={y'｜y∈V};E(μ(G))=E∪{xy'｜xy∈E}∪{wy'｜y'∈V'},称点y'为y的复制点.文章证明了连通图G的Mycielski图存在P4分解当且仅当G的阶数能被3整除.此外我们还给出了Mycielski图的P4分解的一个多项式算法.     

关于二分图的正交因子分解

设 G是二分图 ,fi,gi 是定义在图 G的顶点集 V( G)上的非负整数函数且 gi( x)≤ fi( x) , x∈ V( G) ,1≤ i≤ m。若二分图 G的边能划分成 m个边不交的 [g1,f1]-因子 F1,… [gm,fm]-因子Fm,则称 F={F1,… Fm}是二分图 G的一个 [gi,fi]m1-因子分解 ,又若 H是二分图 G的一个有 m条边的子图 ,若对任意的 1≤ i≤ m有 | E( H)∩ E( Fi) | =1 ,则称 F与 H是正交的。主要研究二分图的正交[gi,fi]m1-因子分解并给出一个结果。     

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.     

图的代数连通度及其点连通度

G是一个简单图.a(G),k(G)分别为G的代数连通度和点连通度,该文刻画了满足a(G)=k(G)的图.G=(V,E)是一个n阶简单图,点连通度为k(G)≤[n/2].H是G的任意最小点割集,则a(G)=k(G)当且仅当对任意u∈H和v∈V\H,有uv∈E.     

二分图中具有正交(g,f)-因子分解的子图

设G是一个二分的(mg+k,mf-k) 图,其中1≤k相似文献