A jump digraph J(D)of a directed multigraph D has as its vertex set being A(D),the set of arcs of D;where(a,b)is an arc of J(D)if and only if there are vertices u1,v1,u2,v2in D such that a=(u1,v1),b=(u2,v2)and v1≠u2....A jump digraph J(D)of a directed multigraph D has as its vertex set being A(D),the set of arcs of D;where(a,b)is an arc of J(D)if and only if there are vertices u1,v1,u2,v2in D such that a=(u1,v1),b=(u2,v2)and v1≠u2.In this paper,we give a well characterized directed multigraph families H1and H2,and prove that a jump digraph J(D)of a directed multigraph D is strongly connected if and only if D?H1.Specially,J(D)is weakly connected if and only if D?H2.The following results are obtained:(ⅰ)There exists a family D of wellcharacterized directed multigraphs such that strongly connected jump digraph J(D)of directed multigraph is strongly trail-connected if and only if D?D.(ⅱ)Every strongly connected jump digraph J(D)of directed multigraph D is weakly trail-connected,and so is supereulerian.(ⅲ)Every weakly connected jump digraph J(D)of directed multigraph D has a spanning trail.展开更多
设D为有向图,T(D)为D的全有向图(Total-digraph),k(D)与p(D)分别为D的幂敛指数(Index of convergence)与周期(Period).本文证明了,1.对任意非平凡有向图D,p(T(D))=1,k(T(D))≤max{2p(D)-1,2k(D)+1},特别地,当D为本原有向图时,k(T(D))≤k...设D为有向图,T(D)为D的全有向图(Total-digraph),k(D)与p(D)分别为D的幂敛指数(Index of convergence)与周期(Period).本文证明了,1.对任意非平凡有向图D,p(T(D))=1,k(T(D))≤max{2p(D)-1,2k(D)+1},特别地,当D为本原有向图时,k(T(D))≤k(D)+1;当D不含有向圈时,k(T(D))=2k(D)-1;当D为有向圈C_n时,k(T(D))=2n-1.2.对任意非平凡强连通图D,k(T(D))≥Diam(D)+1.我们还证明了以上界是不可改进的最好界.展开更多
The h-super connectivity κh and the h-super edge-connectivity λh are more refined network reliability indices than the conneetivity and the edge-connectivity. This paper shows that for a connected balanced digraph D...The h-super connectivity κh and the h-super edge-connectivity λh are more refined network reliability indices than the conneetivity and the edge-connectivity. This paper shows that for a connected balanced digraph D and its line digraph L, if D is optimally super edge-connected, then κ1（L） = 2λ1 （D）, and that for a connected graph G and its line graph L, if one of κ1 （L） and λ（G） exists, then κ1（L） = λ2（G）. This paper determines that κ1（B（d, n） is equal to 4d- 8 for n = 2 and d ≥ 4, and to 4d-4 for n ≥ 3 and d ≥ 3, and that κ1（K（d, n）） is equal to 4d- 4 for d 〉 2 and n ≥ 2 except K（2, 2）. It then follows that B（d,n） and K（d, n） are both super connected for any d ≥ 2 and n ≥ 1.展开更多
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 th...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.展开更多
基金Supported by the National Natural Science Foundation of China(Grant Nos.11761071,11861068)Guizhou Key Laboratory of Big Data Statistical Analysis,China(Grant No.[2019]5103)the Natural Science Foundation of Xinjiang Uygur Autonomous Region(Grant No.2022D01E13)。
文摘A jump digraph J(D)of a directed multigraph D has as its vertex set being A(D),the set of arcs of D;where(a,b)is an arc of J(D)if and only if there are vertices u1,v1,u2,v2in D such that a=(u1,v1),b=(u2,v2)and v1≠u2.In this paper,we give a well characterized directed multigraph families H1and H2,and prove that a jump digraph J(D)of a directed multigraph D is strongly connected if and only if D?H1.Specially,J(D)is weakly connected if and only if D?H2.The following results are obtained:(ⅰ)There exists a family D of wellcharacterized directed multigraphs such that strongly connected jump digraph J(D)of directed multigraph is strongly trail-connected if and only if D?D.(ⅱ)Every strongly connected jump digraph J(D)of directed multigraph D is weakly trail-connected,and so is supereulerian.(ⅲ)Every weakly connected jump digraph J(D)of directed multigraph D has a spanning trail.
文摘设D为有向图,T(D)为D的全有向图(Total-digraph),k(D)与p(D)分别为D的幂敛指数(Index of convergence)与周期(Period).本文证明了,1.对任意非平凡有向图D,p(T(D))=1,k(T(D))≤max{2p(D)-1,2k(D)+1},特别地,当D为本原有向图时,k(T(D))≤k(D)+1;当D不含有向圈时,k(T(D))=2k(D)-1;当D为有向圈C_n时,k(T(D))=2n-1.2.对任意非平凡强连通图D,k(T(D))≥Diam(D)+1.我们还证明了以上界是不可改进的最好界.
基金supported by the natural science foundation of the xinjiang uygur autonomous region(2012211B21)Technology Research and Development Project of Shihezi University(2012 ZRKXYQ-YD07)
基金supported by NSFC(10971255)the Key Project of Chinese Ministry of Education(208161)+1 种基金Program for New Century Excellent Talents in UniversityThe Project-sponsored by SRF for ROCS,SEM
基金Supported by the National Natural Science Foundation of China(No.10271114,No.10301031).
文摘The h-super connectivity κh and the h-super edge-connectivity λh are more refined network reliability indices than the conneetivity and the edge-connectivity. This paper shows that for a connected balanced digraph D and its line digraph L, if D is optimally super edge-connected, then κ1（L） = 2λ1 （D）, and that for a connected graph G and its line graph L, if one of κ1 （L） and λ（G） exists, then κ1（L） = λ2（G）. This paper determines that κ1（B（d, n） is equal to 4d- 8 for n = 2 and d ≥ 4, and to 4d-4 for n ≥ 3 and d ≥ 3, and that κ1（K（d, n）） is equal to 4d- 4 for d 〉 2 and n ≥ 2 except K（2, 2）. It then follows that B（d,n） and K（d, n） are both super connected for any d ≥ 2 and n ≥ 1.
基金Supported by the Ministry of Education and Science, Spainthe European Regional Development Fund (ERDF) under project MTM2008-06620-C03-02the Andalusian Government under project P06-FQM-01649
文摘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.
