首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 78 毫秒
1.
Recently, the primitive symmetric signed digraphs on n vertices with the maximum base 2n and the primitive symmetric loop-free signed digraphs on n vertices with the maximum base 2n-1 are characterized, respectively. In this paper, the primitive symmetric signed digraphs with loops on n vertices with the base 2n-1 are characterized, and then the primitive symmetric signed digraphs on n vertices with the second maximum base 2n-1 are characterized.  相似文献   

2.
A linear directed forest is a directed graph in which every component is a directed path.The linear arboricity la(D) of a digraph D is the minimum number of linear directed forests in D whose union covers all arcs of D. For every d-regular digraph D, Nakayama and P′eroche conjecture that la(D) = d + 1. In this paper, we consider the linear arboricity for complete symmetric digraphs,regular digraphs with high directed girth and random regular digraphs and we improve some wellknown results. Moreover, we propose a more precise conjecture about the linear arboricity for regular digraphs.  相似文献   

3.
In this paper,we study the bases and base sets of primitive symmetric loop-free (generalized)signed digraphs on n vertices.We obtain sharp upper bounds of the bases,and show that the base sets of the classes of such digraphs are{2,3,...,2n-1}.We also give a new proof of an important result obtained by Cheng and Liu.  相似文献   

4.
周波 《东北数学》2001,17(1):57-62
Upper bounds are obtained for fimte i- exponents of non-primitive digraphs of order n with 1≤i≤n, and the extremal cases are eharaeterized.  相似文献   

5.
Let S belong to Zn-{0}.The circulant digraph DCn(S) is a directed graph with vertex set Zn and are set {(i,i s):i∈Zn,s∈S},A.Adam conjectured that DCn(S)≌DCn(T) if and only if T=uS for some unit u mod n.In this paper we prove that the conjecture is true if S is a minimal generating set of Zn and thus determine the full automorphism groups of such digraphs.The methods we employ are new and easy to be understood.  相似文献   

6.
Judicious partitioning problems on graphs ask for partitions that bound several quantities simultaneously,which have received much attention lately.Scott(2005)asked the following natural question:What is the maximum constant cdsuch that every directed graph D with m arcs and minimum outdegree d admits a bipartition V(D)=V_1∪V_2 satisfying min{e(V_1,V_2),e(V_2,V_1)}cdm?Here,for i=1,2,e(V_i,V3-i)denotes the number of arcs in D from V_i to V3-i.Lee et al.(2016)conjectured that every directed graph D with m arcs and minimum outdegree at least d 2 admits a bipartition V(D)=V_1∪V_2 such that min{e(V_1,V_2),e(V_2,V_1)}≥((d-1)/(2(2 d-1))+o(1))m.In this paper,we show that this conjecture holds under the additional natural condition that the minimum indegree is also at least d.  相似文献   

7.
Let D =(V,E)be a primitive digraph.The vertex exponent of D at a vertex v∈V,denoted by exPD(V),is the least integer p such that there is a v→u walk of length p for each u∈V.Following Brualdi and Liu,we order the vertices of D so that exPD(v_1)≤exPD(v_2)≤…≤exPD(v_n).Then exPD(v_k)is called the k- point exponent of D and is denoted by exP_D(k),1≤k≤n.In this paper we define e(n,k):=max{exp_D(k)|D∈PD(n,2)} and E(n,k):= {expD(k)|D∈PD(n,2)},where PD(n,2)is the set of all primitive digraphs of order n with girth 2.We completely determine e(n,k)and E(n,k)for all n,k with n≥3 and 1≤k≤n.  相似文献   

8.
For a strongly connected digraph D the minimum ,cardinality of an arc-cut over all arc-cuts restricted arc-connectivity λ′(D) is defined as the S satisfying that D - S has a non-trivial strong component D1 such that D - V(D1) contains an arc. Let S be a subset of vertices of D. We denote by w+(S) the set of arcs uv with u ∈ S and v S, and by w-(S) the set of arcs uv with u S and v ∈ S. A digraph D = (V, A) is said to be λ′-optimal if λ′(D) =ξ′(D), where ξ′(D) is the minimum arc-degree of D defined as ξ(D) = min {ξ′(xy) : xy ∈ A}, and ξ′(xy) = min(|ω+({x,y})|, |w-({x,y})|, |w+(x) ∪ w- (y) |, |w- (x) ∪ω+ (y)|}. In this paper a sufficient condition for a s-geodetic strongly connected digraph D to be λ′-optimal is given in terms of its diameter. Furthermore we see that the h-iterated line digraph Lh(D) of a s-geodetic digraph is λ′-optimal for certain iteration h.  相似文献   

9.
Denote by c,(s)the circulant digraph with vertex set zn=[0,1,2……n-1]and symbol set s(≠-s)∈zn\[0].let x be the automorphism group of cn(S)and xo the stabilizer of o in x.then cn(S)is arctransitive if and only if xo acts transitively on s.in this paper,co(S)with xo is being the symmetric group is characterized by its symbot set .by the way all the arctransitive clcculant digraphs of degree 2are given.  相似文献   

10.
陈佘喜 《东北数学》2007,23(2):132-140
Let G = (V, E) be a primitive digraph. The vertex exponent of G at a vertex v ∈ V, denoted by expG(v), is the least integer p such that there is a v → u walk of length p for each u ∈ V. We choose to order the vertices of G in the k-point exponent of G and is denoted by expG(k), 1 ≤ k ≤ n. We define the k-point exponent set E(n, k) := {expG(k)| G = G(A) with A ∈ CSP(n)}, where CSP(n) is the set of all n × n central symmetric primitive matrices and G(A) is the associated graph of the matrix A. In this paper, we describe E(n,k) for all n, k with 1 ≤ k ≤ n except n ≡ 1(mod 2) and 1 ≤ k ≤ n - 4. We also characterize the extremal graphs when k = 1.  相似文献   

11.
设D是一个有向图,S是V(D)的子集.在D中推S,是指颠倒D中所有的只有一个端点在S中的弧的方向. Klostermeyer提出了对于任给的一个有向图D,能否通过推点使之成为强连通的有向图的问题.他证明了上述判定问题是NP-完备的.而我们论证了对于任意的二部竞赛图D,如果V(D)的二划分是(X,Y),并满足3≤|X|≤|Y|≤2|X|-1-1, 则可以通过推点使D成为强连通的有向图,而且,|Y|的上界2|X|-1-1是最好可能的.  相似文献   

12.
设D是n阶有向图(允许有环但不允许有重复弧),X C V(D),集指数expD(X)是这样的最小正整数P,使得对D中每个点v,存在从X的至少一个点到V的长为P的途径.若这样的正整数P不存在,则定义expD(X)=∞.D的第k重上广义指数F(D,k):=max{expD(X)| X C V(D),|X|=k},1≤k≤n.如果F(D,k)<∞,则称D是k-上本原的.本文完全刻划了k-上本原对称有向图的第k重上广义指数的极图.  相似文献   

13.
假定Γ是一个有限的、单的、无向的且无孤立点的图,G是Aut(Γ)的一个子群.如果G在Γ的边集合上传递,则称Γ是G-边传递图.我们完全分类了当G为一个有循环的极大子群的素数幂阶群时的G-边传递图.结果为:设图Γ含有一个阶为pn(p是素数,n≥2)的自同构群,且G有一个极大子群循环,则Γ是G-边传递的,当且仅当Γ同构于下列图之一1)pmK1,pn-1-m,0≤m≤n-1;2)pmK1,pn-m,0≤m≤n;3)pmKp,pn-m-1,0≤m≤n-2;4)pn-mCpm,pm≥3,m<n;5)2n-2K1,1;6)pn-1-mCpm,pm≥3,m≤n-1;7)2pn-mCpm,pm≥3,m≤n-1;8)2pn-mK1,pm,0≤m≤n;9)pn-mK1,2pm,0≤m≤n;10)pn-mK2,pm,0<m≤n;11)C(2pn-m,1,pm);12)pkC(2pm-k,1,pn-m),0<k<m,0<m≤n;13)(t-s,2m)C(2m 1/(t-s,2m),1,2n-1-m),其中0≤m≤n-1,2n-2(s-1)≡0(mod 2m),t≡1(mod 2),s(≠)t(mod 2m),1≤s≤2m,1≤t≤2n-1;14)∪p i=1 Ci p n-1,其中Ci p n-1=Ca1a1 [1 (i-1)pn-2]a 1 2[1 (i--1)p n-2]…a 1 (pn-1-1)[1 (i-1)p n-2]≌Cp n-1,i=1,2,…,p;15)∪2 i=1 Ci 2n-1,其中Ci 2n-1=Ca1a 1 [1 (i-1)(2n-2-1)]a1 2[1 (i-1)(2n-2-1)]…a1 (2n-1-1)[1 (i-1)(2n-2-1)]≌C2n-1,i=1,2.  相似文献   

14.
设F为区域D内的只有重级零点的亚纯函数族,H(z)为区域D内的非常数亚纯函数,且存在v∈N,使得对于任意的a∈C,n(D,1/H(z)-a)≤v.如果对于任意的f∈F,f′(z)≠H′(z),那么F在区域D内v阶拟正规.  相似文献   

15.
A digraph D is supereulerian if D has a spanning eulerian subdigraph. BangJensen and Thomass′e conjectured that if the arc-strong connectivity λ(D) of a digraph D is not less than the independence number α(D), then D is supereulerian. In this paper, we prove that if D is an extended cycle, an extended hamiltonian digraph, an arc-locally semicomplete digraph, an extended arc-locally semicomplete digraph, an extension of two kinds of eulerian digraph, a hypo-semicomplete digraph or an extended hypo-semicomplete digraph satisfyingλ(D) ≥α(D), then D is supereulerian.  相似文献   

16.
图G的圈点连通度,记为κ_c(G),是所有圈点割中最小的数目,其中每个圈点割S满足G-S不连通且至少它的两个分支含圈.这篇文章中给出了两个连通图的笛卡尔乘积的圈点连通度:(1)如果G_1≌K_m且G_2≌K_n,则κ_c(G_1×G_2)=min{3m+n-6,m+3n-6},其中m+n≥8,m≥n+2,或n≥m+2,且κ_c(G_1×G_2)=2m+2n-8,其中m+n≥8,m=n,或n=m+1,或m=n+11;(2)如果G_1≌K_m(m≥3)且G_2■K_n,则min{3m+κ(G_2)-4,m+3κ(G_2)-3,2m+2κ(G_2)-4}≤κ_c(G_1×G_2)≤mκ(G2);(3)如果G_1■K_m,K_(1,m-1)且G_2■K_n,K_(1,n-1),其中m≥4,n≥4,则min{3κ(G_1)+κ(G_2)-1,κ(G_1)+3κ(G_2)-1,2_κ(G_1)+2_κ(G_2)-2}≤κ_c(G_1×G_2)≤min{mκ(G_2),nκ(G_1),2m+2n-8}.  相似文献   

17.
一个有向多重图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)$含有生成迹.  相似文献   

18.
Let G =(V, E) be a simple graph with vertex set V and edge set E. A signed mixed dominating function of G is a function f:V∪E→ {-1, 1} such that ∑_(y∈N_m(x)∪{x})f(y)≥ 1for every element x∈V∪E, where N_m(x) is the set of elements of V∪E adjacent or incident to x. The weight of f is w(f) =∑_(x∈V∪E)f(x). The signed mixed domination problem is to find a minimum-weight signed mixed dominating function of a graph. In this paper we study the computational complexity of signed mixed domination problem. We prove that the signed mixed domination problem is NP-complete for bipartite graphs, chordal graphs, even for planar bipartite graphs.  相似文献   

19.
设$K$是实Banach空间$E$中非空闭凸集, $\{T_i\}_i=1^{N}$是$N$个具公共不动点集$F$的严格伪压缩映像, $\{\alpha_n\}\subset [0,1]$是实数列, $\{u_n\}\subset K$是序列, 且满足下面条件 (i)\ 设$K$是实Banach空间$E$中非空闭凸集, $\{T_i\}_i=1^{N}$是$N$个具公共不动点集$F$的严格伪压缩映像, $\{\alpha_n\}\subset [0,1]$是实数列, $\{u_n\}\subset K$是序列, 且满足下面条件 (i)\ 设$K$是实Banach空间$E$中非空闭凸集, $\{T_i\}_i=1^{N}$是$N$个具公共不动点集$F$的严格伪压缩映像, $\{\alpha_n\}\subset [0,1]$是实数列, $\{u_n\}\subset K$是序列, 且满足下面条件 (i)\ 设K是实Banach空间E中非空闭凸集,{Ti}i=1^N是N个具公共不动点集F的严格伪压缩映像,{αn}包括于[0,1]是实数例,{un}包括于K是序列,且满足下面条件(i)0〈α≤αn≤1;(ii)∑n=1∞(1-αn)=+∞.(iii)∑n=1∞ ‖un‖〈+∞.设x0∈K,{xn}由正式定义xn=αnxn-1+(1-αn)Tnxn+un-1,n≥1,其中Tn=Tnmodn,则下面结论(i)limn→∞‖xn-p‖存在,对所有p∈F;(ii)limn→∞d(xn,F)存在,当d(xn,F)=infp∈F‖xn-p‖;(iii)lim infn→∞‖xn-Tnxn‖=0.文中另一个结果是,如果{xn}包括于[1-2^-n,1],则{xn}收敛,文中结果改进与扩展了Osilike(2004)最近的结果,证明方法也不同。  相似文献   

20.
本文提出和研究3个新型的具有离散参数齐次随机场$\{x(m,n)\}$的马氏性问题,求出了它们具有马氏性的充分必要条件.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号