Let D be a weighted digraph with n vertices in which each arc has been assigned a positive number.Let A(D)be the adjacency matrix of D and W(D)=diag(w_(1)^(+),w_(2)^(+),...,w_(n)^(+)).In this paper,we study the matrix...Let D be a weighted digraph with n vertices in which each arc has been assigned a positive number.Let A(D)be the adjacency matrix of D and W(D)=diag(w_(1)^(+),w_(2)^(+),...,w_(n)^(+)).In this paper,we study the matrix A_(α)(D),which is defined as Aα(D)=αW(D)+(1−α)A(D),0≤α≤1.The spectral radius of A_(α)(D)is called the Aαspectral radius of D,denoted byλα(D).We obtain some upper bounds on the Aαspectral radius of strongly connected irregular weighted 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 ...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.展开更多
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 conditi...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.展开更多
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 ...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展开更多
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 ...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.展开更多
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 packa...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.展开更多
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 γ...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 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 h...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.展开更多
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...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.展开更多
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 base...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.展开更多
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 measu...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.展开更多
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 t...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.展开更多
基金Supported by the National Natural Science Foundation of China (Grant No.12001434)The Natural Science Basic Research Program of Shaanxi Province (Grant No.2022JM-006)Chinese Universities Scientific Fund (Grant No.2452020021)
文摘Let D be a weighted digraph with n vertices in which each arc has been assigned a positive number.Let A(D)be the adjacency matrix of D and W(D)=diag(w_(1)^(+),w_(2)^(+),...,w_(n)^(+)).In this paper,we study the matrix A_(α)(D),which is defined as Aα(D)=αW(D)+(1−α)A(D),0≤α≤1.The spectral radius of A_(α)(D)is called the Aαspectral radius of D,denoted byλα(D).We obtain some upper bounds on the Aαspectral radius of strongly connected irregular weighted 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.
基金supported by the National Natural Science Foundation of China (Grant Nos.10571117,60773078)Shu Guang Plan of Shanghai Education Development Foundation (Grant No.06SG42)the Shanghai Leading Academic Discipline Project(Grant No.J50101)
文摘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.
文摘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
文摘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.
文摘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.
基金Project supported by the National Natural Science Foundation of China (Grant Nos.10571117, 60773078)the Shuguang Plan of Shanghai Education Development Foundation (Grant No.06SG42)the Shanghai Leading Academic Discipline Project(Grant No.J50101)
文摘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.
基金Foundation item： Supported by the National Natural Science Foundation of China（61070229） Supported by the Natural Science Foundation of Shanxi Province（2008011010）
文摘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.
基金National Natural Science Foundations of China(No.11272100,No.50865001)
文摘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.
文摘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.
文摘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.
基金Supported by NSFC(11401353)TYAL of ShanxiNatural Science Foundation of Shanxi Province(2016011005)
文摘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.
