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.

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.

<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.

3-Anti-Circulant Digraphs Are α-Diperfect and BE-Diperfect

Let D be a digraph. A subset S of V (D) is a stable set if every pair of vertices in S is non-adjacent in D. A collection of disjoint paths is a path partition of D, if every vertex in V (D) is in exactly one path of . We say that a stable set S and a path partition are orthogonal if each path of contains exactly one vertex of S. A digraph D satisfies the α-property if for every maximum stable set S of D, there exists a path partition such that S and are orthogonal. A digraph D is α-diperfect if every induced subdigraph of D satisfies the α-property. In 1982, Berge proposed a characterization for α-diperfect digraphs in terms of forbidden anti-directed odd cycles. In 2018, Sambinelli, Silva and Lee proposed a similar conjecture. A digraph D satisfies the Begin-End-property or BE-property if for every maximum stable set S of D, there exists a path partition such that 1) S and are orthogonal and 2) for each path P ∈ , either the start or the end of P belongs to S. A digraph D is BE-diperfect if every induced subdigraph of D satisfies the BE-property. Sambinelli, Silva and Lee proposed a characterization for BE-diperfect digraphs in terms of forbidden blocking odd cycles. In this paper, we verified both conjectures for 3-anti-circulant digraphs. We also present some structural results for α-diperfect and BE-diperfect digraphs.

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.

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

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.

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.

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.

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.

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.

基于Digraph-DEMATEL算法的群体决策研究

针对现代企业特别是央企集团决策难度与复杂度进一步提升的问题,以群体决策中专家权重的确定为研究对象,基于DEAMTEL算法原理与复杂网络相关理论,结合多维度的专家群体影响因素剖析,进行算法的拓展研究,构建了Digraph-DEMATEL算法。基于节点加权的加权网络的相关定义,以加权有向图作为专家综合权重的表征,综合考量专家的职级、关联关系、知识水平与技术能力等因素,进行专家影响力的综合度量,以此作为确定专家权重的依据。进一步验证了算法的有效性与可行性,能够为企业群体决策提供一定的理论支撑与实践指导。

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.

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.

Digraph states and their neural network representations

With the rapid development of machine learning,artificial neural networks provide a powerful tool to represent or approximate many-body quantum states.It was proved that every graph state can be generated by a neural network.Here,we introduce digraph states and explore their neural network representations(NNRs).Based on some discussions about digraph states and neural network quantum states(NNQSs),we construct explicitly an NNR for any digraph state,implying every digraph state is an NNQS.The obtained results will provide a theoretical foundation for solving the quantum manybody problem with machine learning method whenever the wave-function is known as an unknown digraph state or it can be approximated by digraph states.

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-[]}.