Sufficient Conditions for Maximally Edge-connected and Super-edge-connected Digraphs Depending on the Size

Let D be a finite and simple digraph with vertex set V(D).The minimum degreeδof a digraph D is defined as the minimum value of its out-degrees and its in-degrees.If D is a digraph with minimum degreeδand edge-connectivity λ,then λ≤δ.A digraph is maximally edge-connected ifλ=δ.A digraph is called super-edge-connected if every minimum edge-cut consists of edges incident to or from a vertex of minimum degree.In this note we show that a digraph is maximally edge-connected or super-edge-connected if the number of arcs is large enough.

On a Class of Supereulerian Digraphs

The 2-sum of two digraphs and , denoted , is the digraph obtained from the disjoint union of and by identifying an arc in with an arc in . A digraph D is supereulerian if D contains a spanning eulerian subdigraph. It has been noted that the 2-sum of two supereulerian (or even hamiltonian) digraphs may not be supereulerian. We obtain several sufficient conditions on and for to be supereulerian. In particular, we show that if and are symmetrically connected or partially symmetric, then is supereulerian.

Bounds on the absorbant number of generalized Kautz digraphs

The generalized Kautz digraphs have many good properties as interconnection network topologies. In this note, the bounds of the absorbant number for the generalized Kautz digraph are given, and some sufficient conditions for the absorbant number of the generalized Kautz digraph attaining the bounds are presented.

Connectivities of Minimal Cayley Coset Digraphs

we prove that the Connectivities of Minimal Cayley Coset Digraphs are their regular degrees. Connectivity of transitive digraphs and a combinatorial propertyof finite groups Ann., Discrete Math., 8 1980 61--64 Meng Jixiang and Huang Qiongxiang On the connectivity of Cayley digraphs, to appear Sabidussi, G. Vertex transitive graphs Monatsh. Math., 68 1969 426--438 Watkins, M. E. Connectivity of transitive graphs J. Combin. Theory, 8 1970 23--29 Zemor, G. On positive and negative atoms of Cayley digraphs Discrete Applied Math., 23 1989 193--195 Department of Mathematics,Xinjiang University,Urumpi 830046.APPLIED MATHEMATICS 3. Statement of Inexact Method Here we assume F to be continuousely differentiable. Inexact Newton method was first studied in the solution of smooth equations (see ). Now, such a technique has been widely used in optimizations, nonlinear complementarity problems and nonsmooth equations (see, and , etc.) In order to establish the related inexact methods,we introduce a nonlinear operator T(x): R n R n . Its components are defined as follows: (T(x)p) i=[HL(2:1,Z;2,Z] (x k+p k) i, if i∈(x k), H i(x k)+ min {(p k) i,F i(x k) Tp k}, if i∈(x k), F i(x k)+F i(x k) Tp k, i∈(x k).(3.1) Then, it is clear that the subproblem (2.5) turns to T(x k)p k=0.(3.2) In inexact algorithm, we determine p k in the followinginexact way ( see ). ‖T(x k)p k‖ υ k‖H(x k)‖,(3.3) where υ k is a given positive sequence. It is then obviously that (3.2),or equivalently (2.5), is a special case of (3.3) corresponding to υ k=0 . In particular, (3.3) can be used as a termination rule of the iterative process for solving (2.5). The following proposition shows the existence of λ k satisfying (2.4). Proposition 3.1. Let F be continuously differe ntiable. υ k is chosen so that υ k for some constant ∈(0,1). Then p k generated by (3.3) is a descent direction of θ at x k, and for some constant σ∈(0, min (1/2,1- holds θ(x k)-θ(x k+λ kp k) 2σλ kθ(x k)(3.4) for all sufficiently small λ k>0. Proof For simplification, we omit the lower subscripts k and denote (x k) i , H i(x k) , (BH(x k)p k) i , etc.by x i , H i , (BHp) i , etc. respectively. To estimate the directional derivative of θ at x k along p k , we divide it into three parts: D p k θ(x k)=H T(x k)BH(x k)p k=T 1+T 2+T 3,(3.5) where T 1=Σ i∈α k H i(BHp) i , T 2=Σ i∈β k H i(BHp) i , T 3=Σ i∈γ k H i(BHp) i . Consider i∈α k= k∪α -(x k) . In this case, we always have H i(BH(x)p) i=H i 2+H i(x i+p i) . If i∈ k , then H i(BHp) i -H i 2+|H i‖(T(x)p) i|. If i∈α -(x k) , then x i<0 . We have either x i+p i 0 , or x i+p i<0 . When x i+p i 0 , we get H i(BH(x)p) i -H i 2 .In the later case, x i+p i<0 , so H i(BH(x)p) i=-H i 2+|H i‖x i+p i|. Then, by elementary computation, we deduce that T 1 -Σi∈α kH i 2+Σ i∈α k|H i‖(T(x)p) i|.(3.6) Received March 1, 1995. 1991 MR Subject Classification: 05C25

A Signed Digraphs Based Method for Detecting Inherently Unsafe Factors of Chemical Process at Conceptual Design Stage

Digraph-based causal models have been widely used to model the cause and effect behavior of process systems. Signed digraphs （SDG） capture the direction of the effect. It should be mentioned that there are loops in SDG generated from chemical process. From the point of the inherent operability, the worst unsafe factor is the SDG having positive loops that means any disturbance occurring within the loop will propagate through the nodes one by one and are amplified gradually, so the system may lose control, which may lead to an accident. So finding the positive loops in a SDG and treating these unsafe factors in a proper manner can improve the inherent safety of a chemical process. This article proposed a method that can detect the above-mentioned unsafe factors in the proc- ess conceptual design stage automatically through the analysis of the SDG generated from the chemical process. A case study is illustrated to show the working of the algorithm, and then a complicated case from industry is studied to depict the effectiveness of the proposed algorithm.

An Explicit Integer Programming Model of the Minimal Spanning Tree Problem for Digraphs with Asymmetric Weights

As far as the minimal spanning tree problem for the digraph with asymmetric weightsis concerned, an explicit integer programming model is proposed, which could be solved successfullyusing the integer programming packages such as LINDO, and furthermore this model is extendedinto the stochastic version, that is, the minimal spanning tree problem for the digraph with theweights is not constant but random variables. Several algorithms are also developed to solve themodels. Finally, a numerical demonstration is given.

Twin domination in generalized Kautz digraphs

Let G = （V,A） be a digraph.A set T of vertices of G is a twin dominating set of G if for every vertex v ∈ V ／ T.There exist u,w ∈ T （possibly u = w） such that （u,v）,（v,w） ∈ A.The twin domination number γ＊（G） of G is the cardinality of a minimum twin dominating set of G.In this paper we consider the twin domination number in generalized Kautz digraphs GK（n,d）.In these digraphs,we establish bounds on the twin domination number and give a sufficient condition for the twin domination number attaining the lower bound.We give the exact values of the twin domination numbers by constructing minimum twin dominating sets for some special generalized Kautz digraphs.

Hamiltonian Cayley Digraphs on Direct Products of Dihedral Groups

We prove that a Cayley digraph on the direct product of dihedral groups D2n × D2m with outdegree two is Hamiltonian if and only if it is connected.

Ordered and Ordered Hamilton Digraphs

A digraph D is k-ordered if for every sequence S：v 1,v 2,…,v k of k distinct vertices,there exists a cycle C such that C encounters the vertices of S in the specified order.In particular,we say that D is k-ordered hamiltonian if for every sequence S：v 1,v 2,…,v k of k distinct vertices,there exists a hamiltonian cycle C such that the vertices of S are encountered on C in the specified order.In this paper,sufficient conditions for digraphs to be ordered and ordered hamiltonian have been given.

A Note on Hamiltionian Decomposition of Cayley Digraphs on Dicyclic Groups

For every dicyclic group,there is a generating set of two elements such that the corresponding Cayley digraph is Harmiltonian decomposable.

2-Competition Index of Primitive Digraphs Using Graph Theory

Recently,scrambling index and competition index are widely applied to stochastic matrices and food webs. By analyzing the relationship of scrambling index and 2-competition index,n-「d/2」+ 1 was proved to be an upper bound of the 2-competition2 index of a primitive digraph with exact d loops in this article.Moreover,the maximum index problem and the index set problem for the 2-competition index of primitive digraphs with minimally strong digraphs were settled.

An efficient parallel algorithm for shortest pathsin planar layered digraphs

This paper presents an efficient parallel algorithm for the shortest path problem in planar layered digraphs that runs in O(log^3n) time with n processors. The algorithms uses a divide and conquer approach and is based on the novel idea of a one-way separator, which has the property that any directed path can be crossed only once.

STUDY ON DIGRAPH OF TREE LENGTH MEASURING DESIGN

Rational measuring design of the tree length is a course to optimize all position of it before bucking. This paper offers the weighted digraph in the digrams and theories to solve the optimal problem of rational measuring of tree length based on experts researches in home and foreign. Sawlines are defined as apexes xd log between two sawlines as a side yn the price of log as weight Wij. It can describe the digraph of the rational measuring design of the tree length T=(X. Y.Wij), which consists of point -set and side-set. Oweing to Wij≥0, using Mr. E. W. Dijkstra's theory, we can obtain the 'path' of maximum profit of the tree length under the best availability of the tree length.

The hamiltonicity on the competition graphs of round digraphs

Given a digraph D =（V, A）, the competition graph G of D, denoted by C（D）, has the same set of vertices as D and an edge between vertices x and y if and only if N;（x）∩N;（y）≠Ф. In this paper, we investigate the competition graphs of round digraphs and give a necessary and sufficient condition for these graphs to be hamiltonian.

ISOMORPHISMS OF CIRCULANT DIGRAPHS OF DEGREE 3

In this paper, we introduce a new approach to characterize the isomor-phisms of circulant digraphs. In terms of this method, we completely determine theisomorphic classes of circulant digraphs of degree 3. In particular, we characterizethose circulant digraphs of degree 3 which don't satisfy Adam's conjecture.

<i>Supereulerian Digraph</i>Strong Products

A vertex cycle cover of a digraph H is a collection C = {C1, C2, …, Ck} of directed cycles in H such that these directed cycles together cover all vertices in H and such that the arc sets of these directed cycles induce a connected subdigraph of H. A subdigraph F of a digraph D is a circulation if for every vertex in F, the indegree of v equals its out degree, and a spanning circulation if F is a cycle factor. Define f (D) to be the smallest cardinality of a vertex cycle cover of the digraph obtained from D by contracting all arcs in F, among all circulations F of D. Adigraph D is supereulerian if D has a spanning connected circulation. In [International Journal of Engineering Science Invention, 8 (2019) 12-19], it is proved that if D1 and D2 are nontrivial strong digraphs such that D1 is supereulerian and D2 has a cycle vertex cover C’ with |C’| ≤ |V (D1)|, then the Cartesian product D1 and D2 is also supereulerian. In this paper, we prove that for strong digraphs D1 and D2, if for some cycle factor F1 of D1, the digraph formed from D1 by contracting arcs in F1 is hamiltonian with f (D2) not bigger than |V (D1)|, then the strong product D1 and D2 is supereulerian.

On the Set of 2 - Common Consequent of Primitive Digraphs with Exact <i>d</i>Vertices Having Loop

Let d and n are positive integers, n≥2,1≤d≤ 2.In this paper we obtain that the set of the 2 - common consequent of primitive digraphs of order n with exact d vertices having loop is{1,2,…, n-[]}.

The Number of Digraphs with Cycles of Length <i>k</i>

In this note, we show that the number of digraphs with n vertices and with cycles of length k, 0 ≤ k ≤ n, is equal to the number of n × n (0,1)-matrices whose eigenvalues are the collection of copies of the entire kth unit roots plus, possibly, 0’s. In particular, 1) when k = 0, since the digraphs reduce to be acyclic, our result reduces to the main theorem obtained recently in [1] stating that, for each n = 1, 2, 3, …, the number of acyclic digraphs is equal to the number of n × n (0,1)-matrices whose eigenvalues are positive real numbers;and 2) when k = n, the digraphs are the Hamiltonian directed cycles and it, therefore, generates another well-known (and trivial) result: the eigenvalues of a Hamiltonian directed cycle with n vertices are the nth unit roots [2].

A Note on Directed 5-Cycles in Digraphs

In this note, it is proved that if α≥0.24817, then any digraph on n vertices with minimum outdegree at least αn contains a directed cycle of length at most 5.

ON ARC-TRANSITIVE CIRCULANT DIGRAPHS

Denote by C n(S) the circulant digraph with vertex set Z n={0,1,2,...,n-1} and symbol set S(≠-S)Z n }. Let X be the automorphism group of C n(S) and X 0 the stabilizer of 0 in X. Then C n(S) is arc transitive if and only if X 0 acts transitively on S. In this paper, C n(S) with X 0| S being the symmetric group is characterized by its symbol set. By the way all the arc transitive circulant digraphs of degree 2 and 3 are given.