笛卡尔积有向图的欧拉覆盖数

如果有向图D包含一个生成欧拉子图,那么有向图D是超欧拉有向图;如果有向图D包含一个生成有向迹,那么有向图D是生成迹有向图。文章定义了有向图D的欧拉覆盖数并用符号ec(D)表示。此外,文章将证明ec(D_1)=1的强连通有向图D_1与ec(D_2)=2的有向图D2做笛卡尔积后的欧拉覆盖数。     

一类型超欧拉有向图

如果一个有向图D包含一个生成欧拉子有向图,那么称D是超欧拉图.Alsatami等人定义了两个有向图的2-和,并且给了两个有向图的2-和是超欧拉图的充分条件.论文将2-和的概念推广到了l-路和,同时给出了一些两个有向图的l-路和是超欧拉图的充分条件.     

一类超欧拉有向图中的超欧拉bypass

设D是严格有向图(无环与重弧),λ(D)是有向图D的弧强连通度,α′(D)表示有向图D的匹配数.如果有向图D中含有一个生成欧拉子图反向一条弧的方向所得的子图,则称有向图D含有一个超欧拉bypass.证明了一个强连通有向图D满足λ(D)≥α′(D)≥5,则有向图D含有一个超欧拉bypass.     

超欧拉路可合并有向图及半完全有向图（英文）

令D是一个严格有向图(无环与重弧),如果D含有一个生成欧拉子有向图,则称D是超欧拉的。文章主要研究路可合并有向图与半完全有向图成为超欧拉的充要条件,利用最大闭迹去寻找矛盾的方法证明了如果一个有向图D是一个路可合并有向图或半完全有向图,则D是超欧拉有向图当且仅当D是强连通的。     

Hamilton有向图的一个新的充分条件

设D是n(≥2)阶强连通有向图.猜想:如果D中每一对不相邻且有公共外邻或公共内邻的顶点x,y都有d(x) d(y)≥2n-1,那么D是Hamilton有向图.文章证明了当n≥7时,若D中每一个不相邻且有公共外邻或公共内邻的顶点x,y都有d(x) d(y)≥(5n)/2-5,则D是Hamilton有向图.当3≤n≤6时,存在非Hamilton有向图D满足D中每一对不相邻且有公共外邻或公共内邻的顶点x,y都有d(x) d(y)≥(5n)/2-5.     

圈的幂图的s-迹连通性

对于图G的任意两个顶点x和y,如果G有一条(x,y)-生成迹,则称图G是迹连通的.给定一个整数s≥0,对于任意点子集X?V(G)并且|X|≤s,如果G-X是迹连通的,则称图G是s-迹连通.设k是一个正整数,图G的k次幂图记为Gk.设t(G)是t一个最大值s使得图G是s-迹连通但不是(s+1)-迹连通,设Cn是一个包含n...     

几乎正则的n-部竞赛图的若干性质

设D是一个有向图,D中所有可能的两点x与y(x与y可以相同)的出度与 入度之差的绝对值的最大值叫做有向图D的非正则性,并记为i(D)。如果i(D)= 0,则称D为正则图;如果i(D)=1,则称D为几乎正则图。本文给出了几乎正则的n -部竞赛图的若干性质。     

扩充竞赛图的控制图

设D=(V,A)是一个有向图,对x,y∈V(D),记O(x)是x控制的顶点的集合,如果O(x)∪O(y)∪{x,y}=V(D),则称x和y控制D。有向图D的控制图记为dom(D),它是一个无向图,顶点集是V(D),且对x,y∈V(D),xy是dom(D)的一条边当且仅当x和y控制D。文章研究扩充竞赛图的控制图,并给出了求解扩充竞赛图的控制图的一个算法。     

广义棱柱中的超欧拉有向图

针对图论中广义棱柱的概念和众多研究成果,作为推广,提出了两个有向图的广义棱柱的概念,研究了这类图的超欧拉性质.基于广义棱柱概念中置换的性质,给出了一种判断广义棱柱是超欧拉有向图的有效工具.证明了两个超欧拉有向图的广义棱柱是超欧拉有向图,另外给出了一类由有向可迹图和超欧拉有向图所构造的广义棱柱是超欧拉有向图的一个特征刻画...     

有向图是极大连通的和超连通的充分条件（英文）

设D是顶点集为V(D)的有限简单有向图.V(D)中的顶点v的度d(v)被定义为v的出度d+(v)和入度d-(v)中的最小值.如果有向图D的最小度为δ,连通度为κ,则κ≤δ.如果κ=δ,则称有向图是极大连通的.对极大连通的有向图D的每个最小点割S,如果D-S要么是非强连通的且至少有一个平凡的强连通分支,要么是平凡的,则称D是超连通的.通过弧数给出有向图或二部有向图在最小度给定时是极大连通的或超连通的充分条件,并举例说明这些条件中的下界是紧的.     

关于Euler生成子图极大边数的一个注记

若图G存在欧拉生成子图,则称G是超欧拉图(supereulerian).常用SL表示全体超欧拉图组成的集合 设G是有n个点的简单图,G∈SL,如果δ(G)≥ 4且δ≥n5-1,则G存在欧拉生成子图H,使得 |E(H) | / |E(G) |≥ 3/5     

蕴含强(p,q)哈密尔顿性的几个条件

利用路收缩技术,证明了,如果有向图D满足下列条件中的任何一个,(1)最小半度δ0(D)≥(n+p+q)/2;(2)D是(p+q+1)强连通有向图,且d+(x)+d+(y)+d-(u)+d-(v)≥2(n+p+q)-1,这里,x,y是任意控制顶点对,u,v是任意被控制顶点对;(3)D的弧数超过(n-1)2+q2+p;那么D是强(p,q)哈密尔顿的.     

有向图的控制圈

采用有向图控制圈的研究方法对有向图控制圈进行了研究 ,证明了 :设 D为 n阶 ( n≥7)强连通有向简单图 ,且对 D的任意弧 ( x,y)有 d-( x) + d+ ( y) >n- 4,那么 D含有控制圈     

BCK—代数中对偶理想的分解

有界BCK-代数的一个子集D叫做一个对偶理想,如果它满足(1)1∈D;(2)N(Ny*Nx)∈D和x∈D蕴涵y∈D,x,y∈X.X的一个对偶理想D有一个既约(质)分解,如果D是有限多个既约(质)对偶理想的交。本文证明下述结果:如果有界BCK-代数X的每一个对偶理想是有限生成的,则X的每个对偶理想有一个既约分解;如果有界BCK-上半格的每个对偶理想是有限生成的,则X的每个对偶理想有一个质分解.     

有向图中爪的一个重要性质

若 u1,…,up 和x为有向图D的顶点,记数列（P1,P2,…,Pp）为满足[x→ u1,u2,…, up]的有向路,使得每个 ui都是不同的,b（Pi）＝ x ,e（Pi）＝ ui 且 Pi 除在点x 外内部顶点均不相交,则称[ x→ u1,u2,…,up ]为有向图 D中的一个爪。我们证明了以下结论：如果[ x→ v1,…,vp－1,y]和[y→ vp ,…,v2p －1]（p≥1）,那么存在一组整数1≤ i1＜…＜ ip ≤2 p－1,使得[x→vi1,…,vip ]。     

素环的T-对称双导

设R是一环 ,称D :R×R→为R的一个T_对称双导 ,如果它满足 (ⅰ )D(x,y) =D(y ,x) ;(ⅱ )D(x+y ,z) =D(x ,z) +D(y ,z) ;(ⅲ )D(xy ,z) =D(x ,z)T(y) +T(x)D(y ,z) .其中T为R的非恒等自同态 .该文研究素环T 对称双性质 ,得出两个主要结论 ,从而推广了他人的结论     

有向图的双超连通性（英文）

简单有向图D(无环与重弧),如果满足每个最小点割都是某个点的出邻点集或入邻点集,则称D是超连通的.在超连通有向图D中,如果存在一个最小点割既是某个点的出邻点集又是某个点的入邻点集,则称D是双超连通的.主要研究了线图双超连通性的充要条件;同时,研究了笛卡尔积与字典积的双超连通性.     

限制弧连通有向图的充分条件

互联网络常以有向图或无向图作为模型,有向图的限制弧连通性能精确度量网络的容错性和可靠性.称有向图D的一个弧子集S是D的限制弧割,如果D-S中存在一个非平凡的强连通分支D1使得D-V(D1)包含至少一条弧.若强连通的有向图D存在限制弧割,则称D是λ′-连通的.λ′-连通图D的最小限制弧割所含的弧数称为D的限制弧连通度,记λ′(D).设D的围长为g,任取长度为g的有向圈Cg=u1u2…ugu1,令ξ(Cg)=min{(sum from i=1 to g)d+(ui)-g,(sum from i=1 to g)d-(ui)-g}且ξ(D)=min{ξ(Cg)}.本文给出了强连通有向图D是λ′(D)≤ξ(D)的一个充分条件.     

有向图的负控制数及其下界

设D=(V,E)为一个有向图,对于函数f:V→{-1,0,1},如果对任意的v∈V,均有f(ND-[v])≥1成立,则称f为图D的一个负控制函数,图D的负控制数γ-(D)=min{w(f)|f是D一个负控制函数}.给出几类有向图的负控制数的值,并得到一般有向图的负控制数的几个下界.     

一类含两棵边不相交生成树的图

若C有一个生成子图是欧拉图,则称G是超欧拉图(supereulerian graph).用SL表示全体超欧拉图的集合.1995年,赖虹建(LAI Hong-jian)、陈志宏(CHEN Zhi-hong)提出一个关于欧拉生成子图边数的公开问题;决定:L=min max G∈SL-{K1}{|E(H)|/|E(G)|} : H是G的欧拉生成子图}定义了一些含两棵边不相交生成树的图Fi(i=1,2,3),证明了如果G∈F3,那么L≥2/3.