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.展开更多
A vertex cycle cover of a digraph <i>H</i> is a collection C = {<em>C</em><sub>1</sub>, <em>C</em><sub>2</sub>, …, <em>C</em><sub><em&g...A vertex cycle cover of a digraph <i>H</i> is a collection C = {<em>C</em><sub>1</sub>, <em>C</em><sub>2</sub>, …, <em>C</em><sub><em>k</em></sub>} of directed cycles in <i>H</i> such that these directed cycles together cover all vertices in <i>H</i> and such that the arc sets of these directed cycles induce a connected subdigraph of <i>H</i>. A subdigraph <i>F</i> of a digraph <i>D</i> is a circulation if for every vertex in <i>F</i>, the indegree of <em>v</em> equals its out degree, and a spanning circulation if <i>F</i> is a cycle factor. Define <i>f</i> (<i>D</i>) to be the smallest cardinality of a vertex cycle cover of the digraph obtained from <i>D</i> by contracting all arcs in <i>F</i>, among all circulations <i>F</i> of <i>D</i>. Adigraph <i>D</i> is supereulerian if <i>D</i> has a spanning connected circulation. In [International Journal of Engineering Science Invention, 8 (2019) 12-19], it is proved that if <em>D</em><sub>1</sub> and <em>D</em><sub>2</sub> are nontrivial strong digraphs such that <em>D</em><sub>1</sub> is supereulerian and <em>D</em><sub>2</sub> has a cycle vertex cover C’ with |C’| ≤ |<em>V</em> (<em>D</em><sub>1</sub>)|, then the Cartesian product <em>D</em><sub>1</sub> and <em>D</em><sub>2</sub> is also supereulerian. In this paper, we prove that for strong digraphs<em> D</em><sub>1</sub> and <em>D</em><sub>2</sub>, if for some cycle factor <em>F</em><sub>1</sub> of <em>D</em><sub>1</sub>, the digraph formed from <em>D</em><sub>1</sub> by contracting arcs in F1 is hamiltonian with <i>f</i> (<i>D</i><sub>2</sub>) not bigger than |<em>V</em> (<em>D</em><sub>1</sub>)|, then the strong product <em>D</em><sub>1</sub> and <em>D</em><sub>2</sub> is supereulerian.展开更多
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 ...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.展开更多
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展开更多
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.展开更多
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.展开更多
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 particul...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.展开更多
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 ...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.展开更多
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 ...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.展开更多
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 eccentricity e(u) of a vertex u is the maximum distance of u to any other vertex of G. A vertex v is an eccentric vertex of vertex u if the distance from u to v is equal to e(u). The eccentric digraph ED(G) of a g...The eccentricity e(u) of a vertex u is the maximum distance of u to any other vertex of G. A vertex v is an eccentric vertex of vertex u if the distance from u to v is equal to e(u). The eccentric digraph ED(G) of a graph (digraph) G is the digraph that has the same vertex as G and an arc from u to v exists in ED(G) if and only if v is an eccentric vertex of u in G. In this paper, we have considered an open problem. Partly we have characterized graphs with specified maximum degree such that ED(G) = G.展开更多
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 ent...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].展开更多
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.
For each pair of positive integers n and k, let G(n,k) denote the digraph whose set of vertices is H = {0,1,2,···, n – 1} and there is a directed edge from a ∈ H to b ∈ H if a ≡ b(mod n). The digrap...For each pair of positive integers n and k, let G(n,k) denote the digraph whose set of vertices is H = {0,1,2,···, n – 1} and there is a directed edge from a ∈ H to b ∈ H if a ≡ b(mod n). The digraph G(n,k) is symmetric if its connected component can be partitioned into isomorphic pairs. In this paper we obtain all symmetric G(n,k)展开更多
We construct Hamilton cycles in connected loopless circulant digraphs of outdegree three with connection set of the form for an integer satisfying the condition for some integer such that , where . This extends work o...We construct Hamilton cycles in connected loopless circulant digraphs of outdegree three with connection set of the form for an integer satisfying the condition for some integer such that , where . This extends work of Miklavi and ?parl, who previously deter-mined the Hamiltonicity of these digraphs in the case where and , to other values of which depend on the generators and .展开更多
文摘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.
文摘A vertex cycle cover of a digraph <i>H</i> is a collection C = {<em>C</em><sub>1</sub>, <em>C</em><sub>2</sub>, …, <em>C</em><sub><em>k</em></sub>} of directed cycles in <i>H</i> such that these directed cycles together cover all vertices in <i>H</i> and such that the arc sets of these directed cycles induce a connected subdigraph of <i>H</i>. A subdigraph <i>F</i> of a digraph <i>D</i> is a circulation if for every vertex in <i>F</i>, the indegree of <em>v</em> equals its out degree, and a spanning circulation if <i>F</i> is a cycle factor. Define <i>f</i> (<i>D</i>) to be the smallest cardinality of a vertex cycle cover of the digraph obtained from <i>D</i> by contracting all arcs in <i>F</i>, among all circulations <i>F</i> of <i>D</i>. Adigraph <i>D</i> is supereulerian if <i>D</i> has a spanning connected circulation. In [International Journal of Engineering Science Invention, 8 (2019) 12-19], it is proved that if <em>D</em><sub>1</sub> and <em>D</em><sub>2</sub> are nontrivial strong digraphs such that <em>D</em><sub>1</sub> is supereulerian and <em>D</em><sub>2</sub> has a cycle vertex cover C’ with |C’| ≤ |<em>V</em> (<em>D</em><sub>1</sub>)|, then the Cartesian product <em>D</em><sub>1</sub> and <em>D</em><sub>2</sub> is also supereulerian. In this paper, we prove that for strong digraphs<em> D</em><sub>1</sub> and <em>D</em><sub>2</sub>, if for some cycle factor <em>F</em><sub>1</sub> of <em>D</em><sub>1</sub>, the digraph formed from <em>D</em><sub>1</sub> by contracting arcs in F1 is hamiltonian with <i>f</i> (<i>D</i><sub>2</sub>) not bigger than |<em>V</em> (<em>D</em><sub>1</sub>)|, then the strong product <em>D</em><sub>1</sub> and <em>D</em><sub>2</sub> is supereulerian.
文摘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.
基金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
文摘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.
文摘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.
基金Supported by the National Natural Science Foundation of China.
文摘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.
文摘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.
基金supported by the National Natural Science Foundation of China(Grant Nos.12001480 and 11871318)the Applied Basic Research Program of Shanxi Province(Grant Nos.201901D211461 and 201901D211462)+2 种基金the Scientific and Technologial Innovation Programs of Higher Education Institutions in Shanxi(Grant No.2020L0554)the Excellent Doctoral Research Project of Shanxi Province(Grant No.QZX-2020001)the PhD Start-up Project of Yuncheng University(Grant No.YQ-2019021)。
文摘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.
文摘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 eccentricity e(u) of a vertex u is the maximum distance of u to any other vertex of G. A vertex v is an eccentric vertex of vertex u if the distance from u to v is equal to e(u). The eccentric digraph ED(G) of a graph (digraph) G is the digraph that has the same vertex as G and an arc from u to v exists in ED(G) if and only if v is an eccentric vertex of u in G. In this paper, we have considered an open problem. Partly we have characterized graphs with specified maximum degree such that ED(G) = G.
文摘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].
文摘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.
文摘For each pair of positive integers n and k, let G(n,k) denote the digraph whose set of vertices is H = {0,1,2,···, n – 1} and there is a directed edge from a ∈ H to b ∈ H if a ≡ b(mod n). The digraph G(n,k) is symmetric if its connected component can be partitioned into isomorphic pairs. In this paper we obtain all symmetric G(n,k)
文摘We construct Hamilton cycles in connected loopless circulant digraphs of outdegree three with connection set of the form for an integer satisfying the condition for some integer such that , where . This extends work of Miklavi and ?parl, who previously deter-mined the Hamiltonicity of these digraphs in the case where and , to other values of which depend on the generators and .