有向跳图的生成欧拉子有向图

一个有向多重图D的跳图$J(D)$是一个顶点集为$D$的弧集,其中$(a,b)$是$J(D)$的一条弧当且仅当存在有向多重图$D$中的顶点$u_1$, $v_1$, $u_2$, $v_2$,使得$a=(u_1,v_1)$, $b=(u_2,v_2)$ 并且$v_1\neq u_2$.本文刻画了有向多重图类$\mathcal{H}_1$和$\mathcal{H}_2$,并证明了一个有向多重图$D$的跳图$J(D)$是强连通的当且仅当$D\not\in \mathcal{H}_1$.特别地, $J(D)$是弱连通的当且仅当$D\not\in \mathcal{H}_2$.进一步, 得到以下结果: (i) 存在有向多重图类$\mathcal{D}$使得有向多重图$D$的强连通跳图$J(D)$是强迹连通的当且仅当$D\not\in\mathcal{D}$. (ii) 每一个有向多重图$D$的强连通跳图$J(D)$是弱迹连通的,因此是超欧拉的. (iii) 每一个有向多重图D的弱连通跳图$J(D)$含有生成迹.     

有向循环图强连通度的下界

为简便计,本文采用文[1]中的定义和符号,而未说明的概念或符号引自[3].本文仅讨论有限、简单有向图. 有向图D=(V,A)称为强连通的,如果对D的任两顶点u与v,在D中同时存在(u,v)—有向路和(v,u)—有向路,C(?)V称为D的点割集,如果D—C非强连通或是单点.D的所含点数最少的点割集称为最小点割集,其阶数定义为D的强连通度,记为k(D)或k. 循环有向图D(n,S)定义如下:     

哈密尔顿性和部分平方图的独立集

设G是一个图,G的部分平方图G*满足V(G*)=V(G),E(G*)=E(G)∪{uv:uv■E(G),且J(u,v)≠■},这里J(u,v)={w∈N(u)∩N(v):N(w)■N[u]∪N[v]}.利用插点方法,证明了如下结果:设G是k-连通图(k2),b是整数,0min {k,(2b-1+k)/2}(n(Y)-1),则G是哈密尔顿图.同时给出图是1-哈密尔顿的和哈密尔顿连通的相关结果.     

关于循环有向图的弧强连通度

设D=(V,A)为简单有向图,其中V=V(D)和A=A(D)分别表示D的顶点集合和弧集合。x,y∈V(D),xy∈A(D)表示D中从x到y的弧。有向图D称为强连通的如果对D中任何两顶点u和v,D中有一条从u到v的有向路,也有一条从v到u的有向路。     

强哈密尔顿连通有向图的一个注记

利用收缩技术,证明了1)阶为n=2k且最小半度至少是k的有向图D是强哈密尔顿连通的,除非D属于某些图类;2)2强连通且包含n个顶点、(n-1)(n-2)+4条弧的有向图是强哈密尔顿连通的,除非D属于某些图类.     

有向P2-路图的结构性质

一个有向图D的有向Pk-路图Pk(D)是通过把D中的所有有向k长路作为点集;两点u= x1x2…xk+1,v=y1y2…yk+1之间有弧uv当xi=yi-1,i=2,3,…,k+1.明显地,当k=1时Pk(D)就是通常的有向线图L(D).在[1,2]中,P2-路图得到完整刻画.在[3]中,Broersma等人研究了有向...     

关于竞赛图中王的一些结果

本文涉及的图都是竞赛图.将用 V(T)、A(T)分别表示竞赛图 T 的顶点集、弧集.设 SV(T),用 T[S]表示在 T 中 S 的导出子图.设 u,v∈V(T),用 uv∈A(T)表示在 T 中有从 u 到 v 的弧,且用O_T(v)={w|w∈V(T),vw∈A(T)},I_T(v)={w|w∈V(T),wv∈A(T)}.1953年,Landau 引进了竞赛图中王的概念:竞赛图T的顶点 v 称为王,如果 v 能通过长至多为2的有向路到达 T 的其它各个顶点.并且证明了,竞赛图中出度最大的     

有向线图的限制性连通度

设D=（y（D）,A（D））是一个强连通有向图．弧集S A（D）称为D的k-限制性弧割,如果D-S中至少有两个强连通分支的阶数大于等于后．最小k-限制性弧割的基数称为k-限制性弧连通度,记作Ak（D）．k-限制性点连通度Kk（D）可以类似地定义．有k-限制性弧割（k-限制性点割）的有向图称为λk-连通（kk-连通）有向图．本文研究有向图D的限制性弧连通度和其线图L（D）的限制性点连通度的关系,证明了对任意λk-连通有向图D,kk（L（D））≤λk（D）,当k=2,3时等式成立;若L（D）是Kk（k-1）连通的,则λk（D）≤Kk（k-1）（L（D））;特别地,若D是一个定向图且L（D）是Kk（k-1）／2．连通的,贝0Ak（D）≤Kk（k-1）,2（L（D））．     

α2-独立数为2的有向图中的迹,路和圈

设α₂(D)=max{|X|:X?V(D)且D[X]不含有向2-圈}是有向图D的α₂ (D)-独立数.在文献[Proc.London Math.Soc.,42 (1981) 231-251]中,Thomassen构造了满足κ(D)=α(D)的非哈密尔顿有向图D,以此证明Chvátal-Erd?s定理在有向图情形下不能得到自然推广.Bang-Jensen和Thomassé提出如下猜想:每一个满足弧强连通度大于等于其独立数的有向图一定包含生成闭迹.对于满足弧强连通度大于等于其α2(D)-独立数的有向图是否包含生成迹这一问题,目前仍未解决.如果对于D中的任意两个顶点x和y,D包含生成(x,y)-迹,或者生成(y,x)-迹,则称有向图D是弱迹连通的.如果对于D中的任意两个顶点x和y,D既包含生成(x,y)-迹又包含生成(y,x)-迹,则称D是强迹连通的.本文在确定两个强连通有向图类M和H的基础上,研究了在满足α₂(D)=2条件下,有向图D的相关结果,并得到以下结论:(ⅰ) D是哈密尔顿的当且仅当D?M.(ⅱ) D是弱迹连通的.(...     

独立集的度和与图的哈密尔顿性

关于哈密尔顿连通图的一个基本结果是Ore给出的：设G是n阶图,若对于任意两个不相邻顶点u和v,有d(u) d(v)≥n 1,则G是哈密尔顿连通的．设G是一个图,对于任意u (?)V(G),令N(U)=∪_(u∈∪)N(u),d(U)=|N(U)|,称d(U)是U的度．本文利用独立集的度和得到如下结果：设s和t是正整数,G是(2s 2t 1)-连通n阶图．若对于任两个强不交独立集S,T,|S|=s,|T|=t,有d(S) d(T)≥n 1．则G是哈密尔顿连通的．同时也得到图的哈密尔顿性的其它相关结果．两个独立集S和T称为强不交的,如果S∪T也是独立集．     

关于赋权图中重圈的一个范型定理

设G=(V, E; w)为赋权图,定义G中点v的权度d_G^w(v)为G中与v相关联的所有边的权和.该文证明了下述定理: 假设G为满足下列条件的2 -连通赋权图: (i) 对G中任何导出路xyz都有w(xy)=w(yz); (ii)对G中每一个与K_1,3或K_1,3+e同构的导出子图T, T中所有边的权都相等并且min{max{d_G^w(x), d^w_G(y)}:d(x,y)=2,x,y∈ V(T)}≥ c/2. 那么, G中存在哈密尔顿圈或者存在权和至少为 c 的圈. 该结论分别推广了Fan^[5], Bedrossian等人^[2]和Zhang等人^[7]的相关定理     

图的能量与哈密尔顿性

设G是一个无向简单图, A(G)为$G$的邻接矩阵. 用G的补图的特征值给出G包含哈密尔顿路、哈密尔顿圈以及哈密尔顿连通图的充分条件; 其次用二部图的拟补图的特征值给出二部图包含哈密尔顿圈的充分条件. 这些结果改进了一些已知的结果.     

2-控制数和连通2-控制数相等的图(英文)

任意一个图G =(V ,E) ,S是V(G)的子集 ,如果对每一个顶点u∈V-S都存在顶点v∈S ,使得d(u ,v) ≤ 2 ,则称S为G的一个 2 控制 .称最小的 2 控制集的顶点个数为G的 2 控制数 ,记为γ2 (G) .如果G的一个 2 控制集S的生成子集〈S〉是一个连通图 ,则称S为G的一个连通 2 控制集 .称最小的连通 2 控制集的顶点个数为G的连通 2 控制数 ,记为γc2 (G) .本文论述了树和单圈图中 2 控制数和连通 2 控制数相等的充分必要条件 .     

广义de Bruijn和Kautz有向图的双向控制集

设G=(V,A)是一个有向图,其中V和A分别表示有向图G的点集和弧集.对集合TV(G),如果对于任意点v∈V(G)\T,都存在点u,w∈T(u,w可能是同一点)使得(u,v),(v,w)∈A(G),则称T是G的一个双向控制集.有向图G的双向控制数γ~*(G)是G的最小双向控制集所含点的数目.提出了广义de Bruijn和Kautz有向图的双向控制数的新上界,改进了以前文献中提出的相关结论.此外,对某些特殊的广义de Bruijn和Kautz有向图,通过构造其双向控制集,进一步改进了它们双向控制数的上、下界.     

有向路和有向圈的控制集数

1引言设G=(V,E)为无向图．子集D (?)V(G)是无向图G的控制集,如果对于任意的y,∈V(G)-D,都存在x∈D,使xy∈E(G)．G的控制集D是G的分裂控制集,如果G中由V(G)-D导出的子图G〈V(G)-D〉是不连通的．G的一个控制集D是G的一个强(弱)控制集,若dG(x)≥d_G(y)(d_G(x)≤d_G(y)),其中d_G(x)表示G中与点x关联的边数．对于有向图H=(V,A),子集D(?)V(H)称为H的控制集,如果对于任意的y∈     

一类非线性双曲-抛物耦合问题的A.D.I.Galerkin方法

1　引　言考虑三维非线性双曲 -抛物耦合初边值问题 :utt- . (a1 (X,t,u) u) +b1 (X,t,u,v) . u　　　　 +α1 e. v =f(X,t,u,v) ,X∈Ω,t∈ J.vt-a2 Δv +b2 (X,t,u,v) . v　　　　 +α2 e. ut=g(X,t,u,v) ,X∈Ω,t∈ J.u(X,t) =v(X,t) =0 , X∈ Ω ,t∈ J.u(X,0 ) =u0 (X) ,ut(X,0 ) =ut0 (X) ,v(X,0 ) =v0 (X) ,X∈Ω.(1 .1 )其中 ,X=(x1 ,x2 ,x3) ,Ω=(c1 ,d1 )× (c2 ,d2 )× (c3,d3)为 R3中矩形区域 ,边界 Ω . J=[0 ,T] ,T>0为一正常数 .b1 ,b2 ,f,g均为已知光滑函数 (其中 b1 ,b2 为向量函数 ) ,且关于 u,v满足 L…     

边色数的分类及其有关性质

设图G为简单连通图,由Vizing定理知:Δ(G)≤x′(G)≤Δ(G) 1,其中Δ(G)表示图G的最大顶点次,x′(G)为图G的边色数。若x′(G)=Δ(G),则称G为第一类图,记为G∈C~1;若x′(G)=Δ(G) 1,则称G为第二类图,记为G∈C~2。其他图论术语见一般参考书。一边e(或者顶点v)称为临界的,如果成立x′(G)>x′(G\e)(或者x′(G)>x′(G\v))。图G称为是临界的,如果G∈C~2,且G的每一边是临界的。对于v∈V(G),令d~*(v)=|{u|(v,u)∈E(G)且d(u)=Δ(G)}|。设F={u|d(u)=Δ(G),u∈V(G)},记G_Δ=G[F]。令图G_Δ的圈秩数为b(G_Δ)。     

三类特殊图的(强)彩虹连通数

如果一条路上的任意两条边均染不同颜色,则称这条路是彩虹路.如果在图G的任意两个顶点间都存在一条彩虹路,就称图G是彩虹连通的.对于一个连通图G,保证它是彩虹连通所需的最少颜色数就是G的彩虹连通数,记为rc(G).一条彩虹(u,v)-测地线是指图G中一条长度为d(u,v)的彩虹(u,v)-路,其中d(u,v)表示图G中u,v两点的距离.如果在图G的任意两个顶点间都存在一条彩虹测地线,就称图G是强彩虹连通的.对于一个连通图G,保证它是强彩虹连通所需的最少颜色数就是G的强彩虹连通数,记为src(G).这篇文章主要研究了三类特殊图的(强)彩虹连通数,并得到了它的精确值.     

图的下测地数和上测地数

对于图G(或有向图D)内的任意两点u和v,u—v测地线是指在u和v之间(或从u到v)的最短路．I(u,v)表示位于u—v测地线上所有点的集合,对于S(?)V(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的定向图}．对于u∈V(G)和v∈V(H),G_u H_v表示在u和v之间加一条边所得的图．本文主要研究图G_u H_v的测地数和上(下)测地数．     

Kronecker乘积图的超连通性(英文)

设G1和G2是两个连通图,则G1和G2的Kronecker积G1×G2定义如下:V(G1×G2)=V(G1)×V(G2),E(G1×G2)={(u1,v1)(u2,v2):u1u2∈E(G1),v1v2∈E(G2)}.我们证明了G×Kn(n≥4)超连通图当且仅当κ(G)n>δ(G)(n 1),其中G是任意的连通图,Kn是n阶完全图.进一步我们证明了对任意阶至少为3的连通图G,如果κ(G)=δ(G),则G×Kn(n≥3)超连通图.这个结果加强了郭利涛等人的结果.