一类亚几乎唯一泛圈图

设G是阶为n的简单Hamilton图,若存在不同的p,q(3≤p相似文献   

关于2G与路的并的优美标号

设G是有q条边的优美二部图,优美标号为θ,pm是有m条边的简单路,C=k 0〈k〈q,k≠θ（v）,v∈V（G{）},a=maxC,b=minC,h=min q-a＋2,b{}＋2.图G∪G∪Pm是两个图G与一条简单通路的不交并.证明了：当m=1或m≥h时,图G∪G∪Pm是优美的.应用此结论,得到：对所有的s≥2,t≥2,当m=1或m≥3时,图Ks,t∪Ks,t∪Pm是优美的.     

三路树P（2m,2m,2m）是边幻图的证明

令简单图G－（V,E）是有p个顶点q条边的图,假设G的顶点和边由1,2,3,,…,p q所标号,且f:VUE→{1,2,…,p q}是一个双射,如果对所有的边xy,f(x) f(y) f(xy)是常量,则称图G是边幻图（edge-magic),文[1]中猜测树是边幻图,本文证明了三路树P（m,n,t）当m,n,t为偶数且相等时为边幻图。     

k连通［s,t］图的Hamiltion连通性

若图G的任意个s顶点的导出子图至少有t条边,则称图G为[s,t]图．[s,t]图的概念可视为图的独立数概念的推广．本文证明：若图G是k连通[k＋1,2]（k≥2）图,则G或者是Hamilton连通的或者同构于Kk∨Gk．由此可以推出,若图G的阶是n（n≥3）,α（G）≤κ（G）－1,则G是Hamilton连通的．     

S(7，n)的k-边优美的图标号Z

设图G＝(V,E),其中|V|＝p,|E|＝q.对于k∈N,如果存在一个双射f：E→{k,k＋1,…,k＋q－1},使得它的导出映射f＋：V→Zp,uMT ExtraaAp(u,v) mod p也是一个双射,则称图G是k-边优美的.对于所有的满足G为k-边优美图的非负整数k构成的集合称为图G的边优美指标集.本文根据轮图的特殊性质,讨论了S(7,n)为k-边优美图的必要条件.根据所得的必要条件,利用递归的方法构造S(7,n)的k-边优美图标号并给出详细证明,从而完全解决了当n为偶数时S(7,n)的边优美指标集问题.     

S(3,n)的k-边优美的图标号

设k为非负整数,G是一个p点q边图,如果将G的边用k,k+1,k+2,…,k+q-1进行标号,而顶点标号模p运算后各不相同,则称G是k-边优美的.对于所有满足G为k-边优美图的非负整数k所构成的集合称为图G的边优美指标集.该文给出了图G=(V,E)为k-边优美的定义,根据轮图的特殊性质,讨论了S(3,n)为k-边优美图的必要条件.根据所得的必要条件,利用递归的方法构造S(3,n)的k-边优美图标号并给出详细证明,从而完全解决了当n为偶数时S(3,n)的边优美指标集问题.     

图中具有特定性质的连通的[k,k＋1]-因子存在性的一个度条件

设k是一个正整数,图G是一个具有n个顶点的图,其中n≥4k＋8,nk是偶数且δ（G）〉;k＋1。我们证明如果图G的任意两个不相邻的顶点u,v都有max{dG（u）,dG（v）}〉;n/2,则图G含有一个连通的[k,k＋1]-因子不包含任意指定的边。     

边无关数为q的n阶树的谱半径的第三大值

设G为有限无向简单图,G的邻接矩阵的特征值称为G的特征值,G的最大特征值称为G的谱半径．二分图的特征值在量子化学中有意义，因而研究二分图的特征值有重要的实用价值．K1^l,k(k≥l≥1)记星图K1．k的l个悬挂点各接出一条悬挂边所得的图．Tn(q)表示边无关数为q(≥5)的n阶树的集合．(1．1)T(q-3，n-2q 1)∈Tn(q)为K1^q-2,n-q-l的某个2度顶点上接出一条路P2所得的图．给出了Tn(q)中树的谱半径的第三大值。并证明了：当n-2q=1时,取得该值的唯一的树为K1^q，q；当n-2q≥2时，取得该值的树为(1，1)T(q-3,n-2q 1)．     

二分图中存在包含经过给定边的大国的2-因子的度条件

该文主要证明了若G=（V1，V2：E）是一个满足｜V1｜=｜V2｜=n≥sk的二分图，其中k,s,n为3个正整数且k≥2,s≥4，如果σ1,1（G）σ2[（1-1/s）n＋k]，那么对G的任意k条独立边e1，…,ek,G有一个包含k个点不交的圈C1,…Ck的2-因子，使得ei∈E（Ci）,且｜Ci｜≥2s.     

Erd(o)s-sòs猜想的一个结果

借助图的包装理论,证明了当k=n-3时,Erd(o)s-Sòs猜想(如果G是一个有g条边的,n阶简单图,并且q>1/2 n(k-1),则G包含具有k条边的所有树)成立.     

两类并图的优美标号

讨论2n个优美二分图与一条通路并的优美性,得到如下结论:设二分图G=(X,Y,E)优美,优美标号为θ,边数为q,a=max{k|0相似文献   

用非交换图刻画L3(q)

令G是一个有限群,其非交换图▽（G）如下定义：顶点集合▽（G）是G／Z（G）,当两条边x与y的换位子不等于单位元时x与y相连.我们证明了如果G是一个有限群,且▽（G）≌▽（M）,其中M=L3（q）,q=pn,p是素数n∈N,则G≌M.     

联结数与分数（k，n’）一临界消去图

设G是一个图,若删除G中任意n’个顶点的剩余子图依然是分数k-消去图,则称G为分数（k,n＇）-临界消去图．笔者证明了若k≥2,n,≥0,bind（G）≥^（n＇＋1）且6（G）≥k＋n＇＋1,则G是分数（k,n＇）-临界消去图．     

S(7,n)的k-边优美的图标号

设图G=(V,E),其中|V|=p,|E|=q.对于k∈N,如果存在一个双射f:E→{k,k+1,…,k+q-1},使得它的导出映射f+:V→Zp,ua∑(u,v)∈Ef(u,v)mod p也是一个双射,则称图G是k-边优美的.对于所有的满足G为k-边优美图的非负整数k构成的集合称为图G的边优美指标集.本文根据轮图的特殊性质,讨论了S(7,n)为k-边优美图的必要条件.根据所得的必要条件,利用递归的方法构造S(7,n)的k-边优美图标号并给出详细证明,从而完全解决了当n为偶数时S(7,n)的边优美指标集问题.     

二部竞赛图中的最长圈问题

若有向图T满足条件:uv (∈)A(T)且存在一点w使得uw ∈A(T),wv∈A(T)则d-(u)+d+(v)≥n,称图T满足G(n)条件.在本文中,我们讨论了如果T(p,q)二部竞赛图满足G(n)条件且强连通,则T(p,q)包含一条长至少为2min{n+1,p,q}的圈,除非n为偶数且T(p,q)同构于一类图族B(k1,k2,k3,n/2),k1≥n/2,i=1,2,3,及特殊竞赛图的最长圈问题.     

高度平面图的列表L（p，g）-标号

如果平面图G的最大度△（G）=｜V（G）｜-k,k=1,2,…,则称G为一个hk-图,k=1,2的hk-图称为高度平面图．研究了高度平面图G的列表L（p,q）-标号问题,给出了高度平面图G的列表L（p,q）-标号数λl（G;p,q）的上界,并对hi-图证明了λl（G;p,q）≤（2q-1）△＋6（p—q）;对h2-图有λl（G;p,q）≤（2q-1）△＋8p-6q-1．     

直径为3围长为6的二分图

讨论直径为d围长为g（＝2d）的二分图的结构,得到的结果为：若G是二分图,d（G）＝3,g（G）＝6,则G是图θ3^n,n≥2或（k,6）－图,k≥3,这里θ3^n（n≥2）是由n条内部不交的3－长路构成的图,（k,6）－图（k≥3）是具有度数k、围长6和顶点数no(k,6）的图。     

关于图的算术标号

一个（p,q）-图G称为是（k,d）-算术的,若它的顶点可标以不同非负整数,使得它的边的赋值（由它的端点标号之和得到）能排成算术级数k,k＋d,k＋2d,…,k＋（q-1）d.本文综述了算术图的有关结果.     

线图上次泛圈性的两条独立边的度和条件

给定一个n（n≥72）阶图G,满足q1（G）=min{d（u）＋d（v）：uv∈E（G）}≥8,得出结论：若围长g（G）≥5且q2（G）=min{d（ei）＋d（ej）：ejej E（L（G））且ei,ej∈E（G）}〉2√2n=1时,L（G）是次泛圈图;若围长g（G）≥4且q2^2（G）-2q2（G）〉8n时,L（G）是次泛圈图,而且2√2n＋1,8n这两个界都是最好可能的。     

基于完全二分图矩阵的△（G）-边着色求解完全图K4n的完备匹配

给出了边矩阵和循环赛图的定义，提出了基于n（n-1）／2个完全二分图矩阵的△（G’）-边着色求解完全图k4n的完备匹配Mi的算法。阐明了循环赛图程的构造的基本思路，介绍了完全图K30的△（G＇）个完备匹配Mi的划分过程。