Search

The multiset of unlabeled subdigraphs of a digraph D obtained by deleting one vertex at a time is called its deck. Digraphs having the same deck are called hypomorphic. Two digraphs D and E are called S-isomorphic if either they are isomorphic or there exists a digraph F with a pair of vertices u and v such that there is no arc joining them in F and D ≅ F + uv and E ≅ F + vu (where uv denotes an arc directed from u to v). S.M. Ulam conjectured (1960) that two hypomorphic graphs are always isomorphic and it is still open. Ten infinite families of pairs of hypomorphic but non-isomorphic digraphs on ≥ 5 vertices and seven such pairs other than them are now known. Their effect on the truth of Ulam’s conjecture is investigated and proved that in all these pairs except four, the two digraphs in the pair are S-isomorphic. These exempted pairs are of five or six vertex digraphs. Are all pairs of hypomorphic digraphs on seven or more vertices S-isomorphic? If yes, then Ulam’s conjecture is true.

Traffic flow prediction is an important part of the intelligent transportation system. Accurate multi-step traffic flow prediction plays an important role in improving the operational efficiency of the traffic network. Since traffic flow data has complex spatio-temporal correlation and non-linearity, existing prediction methods are mainly accomplished through a combination of a Graph Convolutional Network (GCN) and a recurrent neural network. The combination strategy has an excellent performance in traffic prediction tasks. However, multi-step prediction error accumulates with the predicted step size. Some scholars use multiple sampling sequences to achieve more accurate prediction results. But it requires high hardware conditions and multiplied training time. Considering the spatiotemporal correlation of traffic flow and influence of external factors, we propose an Attention Based Spatio-Temporal Graph Convolutional Network considering External Factors (ABSTGCN-EF) for multi-step traffic flow prediction. This model models the traffic flow as diffusion on a digraph and extracts the spatial characteristics of traffic flow through GCN. We add meaningful time-slots attention to the encoder-decoder to form an Attention Encoder Network (AEN) to handle temporal correlation. The attention vector is used as a competitive choice to draw the correlation between predicted states and historical states. We considered the impact of three external factors (daytime, weekdays, and traffic accident markers) on the traffic flow prediction tasks. Experiments on two public data sets show that it makes sense to consider external factors. The prediction performance of our ABSTGCN-EF model achieves 7.2%–8.7% higher than the state-of-the-art baselines.

We give a fully dynamic single-source shortest paths data structure for planar weighted digraphs with O ˜ ( n 4 / 5 ) worst-case update time and O ( log 2 ⁡ n ) query time. Here, a single update can either change the graph by inserting or deleting an edge, or reset the source s of interest. All known non-trivial planarity-exploiting exact dynamic single-source shortest paths algorithms to date had polynomial query time. We then extend our approach, obtaining a data structure that can maintain a planar digraph under edge insertions and deletions, and is capable of returning the identifier of the strongly connected component of any query vertex. The worst-case update and query time bounds are the same as for our single-source distance oracle. To the best of our knowledge, this is the first fully dynamic strong-connectivity algorithm achieving both sublinear update time and polylogarithmic query time for an important class of digraphs.

In 1972, Cvetkovic proved that if G is an n-vertex simple graph with the chromatic number k, then its spectral radius is at most the spectral radius of the n-vertex balanced complete k-partite graph. In this paper, we analyze the characteristic polynomial of a digraph D to prove a tight upper bound for the spectral radius of D in terms of the number of vertices and the chromatic number of D; we also characterize when equality holds. This provides a simple proof of a result by Lin and Shu [6] .

Session-based recommendation, which aims to predict subsequent user actions based on anonymous sessions, plays a significant role in many online services. Existing methods construct each session as a digraph and then capture the rich transition relationship of items by using graph neural networks. However, their ability to obtain the user’s static intentions is insufficient and they suffer from improper combinations of different user intentions. In this study, we propose a dynamic and static intentions integrated graph neural network (DSGNN) for session-based recommendation, in which the user’s intentions captured by a digraph and an undigraph are comprehensively considered to enhance the recommendation performance. The prediction results from the dynamic and static intentions are combined using a lightweight gating network, which reduces the conflict between the two kinds of information. Furthermore, the weighted inner product is designed to alleviate the impact of the value of the item representation vectors. Extensive experiments on three real-world datasets show that the DSGNN outperforms other state-of-the-art methods and demonstrates that the components in our model are effective.

This paper studies the differential privacy-preserving problem for multi-agent systems (MASs) in the presence of antagonistic information over signed digraph. As for the structurally balanced case, an e -differential privacy algorithm is proposed, upon which some sufficient conditions guaranteeing almost sure bipartite consensus are given. Based on the above scheme, the tradeoff between the system performance and the privacy guarantee is elaborated, and the optimal noise is also devised. Moreover, the proposed privacy preserving scheme is further applied to the scenario of structurally unbalanced graph, where a criterion with respect to almost sure stability of the considered system is derived, as well as the privacy preserving condition. This extends the balanced interaction scenario, and consequently the cooperative multi-agent systems. Finally, numerical simulations are presented to demonstrate the effectiveness of our results.

A cycle with four blocks C ( k 1 , k 2 , k 3 , k 4 ) is an oriented cycle formed of four blocks of lengths k 1 , k 2 , k 3 and k 4 respectively. We conjecture that for every positive integers k 1 , k 2 , k 3 , k 4 , there is an integer g ( k 1 , k 2 , k 3 , k 4 ) such that every strongly connected digraph with chromatic number greater than g ( k 1 , k 2 , k 3 , k 4 ) contains a subdivision of C ( k 1 , k 2 , k 3 , k 4 ) . As evidence, we prove this conjecture for k 2 = k 3 = k 4 = 1 .

Seymour’s Second Neighborhood Conjecture (SSNC) asserts that every finite oriented graph has a vertex whose second out-neighborhood is at least as large as its first out-neighborhood. Such a vertex is called a Seymour vertex. In this paper, we prove that SSNC holds for some particular cases of m -free digraphs (digraphs having no directed cycles with length at most m ). A digraph D = ( V , E ) is k -transitive if for any directed u v -path of length k , we have ( u , v ) ∈ E . For k ≤ 6 , we prove that every k -transitive digraph with no sink (vertex of out-degree zero) has at least two Seymour vertices. A digraph D = ( V , E ) is k -anti-transitive if for any directed u v -path of length k , we have ( u , v ) ∉ E . For k ≤ 4 , we prove that every k -anti-transitive digraph with no sink has at least two Seymour vertices. In k -transitive and k -anti-transitive digraphs, the Seymour vertices found are explicitly identified.

Let D be a digraph and let α ( D ) , α ′ ( D ) and λ ( D ) be independence number, the matching number and the arc-strong connectivity of D , respectively. Bang-Jensen and Thommasse in 2011 conjectured that every digraph D with λ ( D ) ≥ α ( D ) is supereulerian. In [J. Graph Theory, 81(4), (2016) 393-402], it is shown that every digraph D with λ ( D ) ≥ α ′ ( D ) is supereulerian. In this paper, we introduced the symmetric core of a digraph and use it to show that each of the following holds for a strong digraph D on n ≥ 3 vertices with λ ( D ) ≥ α ′ ( D ) − 1 . ( i ) There exists a family D ( n ) of well-characterized digraphs such that for any digraph D with α ′ ( D ) ≤ 2 , D has a spanning trial if and only if D is not a member in D ( n ) . ( i i ) If α ′ ( D ) ≥ 3 , then D has a spanning trail. ( i i i ) If α ′ ( D ) ≥ 3 and n ≥ 2 α ′ ( D ) + 3 , then D is supereulerian. ( i v ) If λ ( D ) ≥ α ′ ( D ) ≥ 4 and n ≥ 2 α ′ ( D ) + 3 , then for any pair of vertices u and v of D , D contains a spanning ( u , v ) -trail.

Let H be a digraph possibly with loops and D a digraph without loops with a coloring of its arcs c : A ( D ) → V ( H ) ( D is said to be an H -colored digraph). A directed path W in D is said to be an H -path if and only if the consecutive colors encountered on W form a directed walk in H . A subset N of vertices of D is said to be an H -kernel if (1) for every pair of different vertices in N there is no H -path between them and (2) for every vertex u in V ( D ) ∖ N there exists an H -path in D from u to N . Under this definition an H -kernel is a kernel whenever A ( H ) = 0 ; an H -kernel is a kernel by monochromatic paths whenever A ( H ) = { ( u , u ) : u ∈ V ( H ) } ; an H -kernel is a properly colored kernel whenever H has no loops and an H -kernel is a kernel by rainbow paths whenever H has no directed cycles. Let k be an integer, with k ≥ 2 . D is k -quasi-transitive if for every pair of vertices u and v of D , the existence of a directed path of length k from u to v implies that { ( u , v ) , ( v , u ) } ∩ A ( D ) ≠ 0 . In Galeana-Sanchez and O’Reilly-Regueiro (2013), in Delgado-Escalante et al. (2018) and in Galeana-Sanchez and Rojas-Monroy (2006) the authors establish sufficient conditions to guarantee the existence of kernels by monochromatic paths in 3-quasi-transitive digraphs, the existence of properly colored kernels in 2-quasi-transitive digraphs and the existence of kernels in 2-quasi-transitive digraphs, respectively. In this paper we investigate the problem of the existence of H -kernels in quasi-transitive and in 3-quasi-transitive digraphs by means of a partition of V ( H ) . We give some examples which show that each hypothesis in the main result for quasi-transitive digraphs is tight.

This paper focuses on the mean square cluster consensus of nonlinear multi-agent systems with Markovian switching topologies and communication noise via pinning control technique. Network topology can take weaker conditions in each cluster but an extra balanced condition is also needed. A time-varying control gain will be introduced to eliminate the effect of stochastic noise. For the case of fixed topology, if the induced digraph of each cluster has a directed spanning tree, the sufficient conditions for the mean square cluster consensus can be obtained. For the case of Markovian switching topologies, if the induced digraph of union of the Laplacian matrix of each mode has a directed spanning tree, the mean square cluster consensus conclusion can be derived. Particularly, if the elements of transition probability of Markov chain are partly unknown, we can also obtain the same conclusion under the same conditions. Finally, two examples are given to illustrate our results.

Spectral characterization of graphs is a well-studied topic in spectral graph theory which has received a lot of attention from researchers. The spectral characterization of oriented graphs, however, is less studied so far. Given a simple undirected graph G with an orientation σ, the oriented graph G σ is a digraph obtained from G by assigning to every edge of G a direction according to σ. An oriented graph G σ is self-converse if it is isomorphic to its converse ( G σ ) T , a graph obtained from G σ by reversing each directed edge in G σ . We denote by S ( G σ ) the skew-adjacency matrix of G σ . For two oriented graphs G σ and H τ with skew-adjacency matrices S ( G σ ) and S ( H τ ) , respectively, we say G σ is R -cospectral to H τ , if for any t ∈ R , two matrices t J − S ( G σ ) and t J − S ( H τ ) have the same spectrum, where J is the all-one matrix. An oriented graph G σ is said to be determined by the generalized skew spectrum (DGSS for short) if, any oriented graph R -cospectral to G σ is isomorphic to G σ . Oriented graphs that are DGSS must be self-converse. In this paper, we give a simple arithmetic condition for a self-converse oriented graph being DGSS, which provides an analogue of a similar result for ordinary graphs; see [15] . More precisely, let G σ be a self-converse oriented graph with skew-adjacency matrix S ( G σ ) , and W ( G σ ) = [ e , S ( G σ ) e , ⋯ , S n − 1 ( G σ ) e ] (e is the all-one vector) be the skew-walk-matrix. We show that if 2 − ⌊ n 2 ⌋ det ⁡ W ( G σ ) is odd and square-free, then G σ is DGSS. Moreover, we also illustrate that our result is the best possible in certain sense.

This paper considers the leader-following consensus problem for delayed neural networks with multi-layer signed digraph topologies. Both structurally balanced and unbalanced topologies are considered. By using the structural balance theory and the pinning control strategy, some sufficient conditions are given to guarantee that the bipartite leader-following consensus can be reached in structurally balanced multi-layer signed neural networks, which depend on the node dynamics and the topology of the multi-layer signed network. In addition, a scheme is designed for selecting the pinning nodes and gains of each layer to achieve bipartite leader-following consensus. When the multi-layer signed network is structurally unbalanced, the asymptotic stability of the neural network is investigated by decomposing the structurally unbalanced network into a structurally balanced subgraph and some special edges. The conditions proposed in this paper are also suitable for addressing the consensus problem of traditional single layer signed neural networks. Numerical examples are given to illustrate the correctness and effectiveness of the proposed theorems and algorithms.

We define an alternating zeta function of a digraph D, and give its determinant expression. We present a decomposition formula for the alternating zeta function of a group covering of D. Furthermore, we introduce an alternating L-function of D, and present a determinant expression of it. As a corollary, we present a decomposition formula for the alternating zeta function of a group covering of D by its alternating L-functions.

The energy of a graph G, E ( G ) , is the sum of absolute values of the eigenvalues of its adjacency matrix. This concept was extended by Nikiforov to arbitrary complex matrices. Recall that the trace norm of a digraph D is defined as, N ( D ) = ∑ i = 1 n σ i , where σ 1 ≥ ⋯ ≥ σ n are the singular values of the adjacency matrix of D. In this paper we would like to present some lower and upper bounds for N ( D ) . For any digraph D it is proved that N ( D ) ≥ rank ( D ) and the equality holds if and only if D is a disjoint union of directed cycles and directed paths. Finally, we present a lower bound on σ 1 and N ( D ) in terms of the size of digraph D.

A directed path in a digraph is proper if any two consecutive arcs on the path have distinct colors. An arc-colored digraph D is proper connected if for any two distinct vertices x and y of D, there are both proper ( x , y ) -directed paths and proper ( y , x ) -directed paths in D. The proper connection number p c → ( D ) of a digraph D is the minimum number of colors that can be used to make D proper connected. Obviously, if a digraph has a proper connection number, it must be strongly connected, and p c → ( D ) = 1 if and only if D is complete. Magnant et al. showed that p c → ( D ) ≤ 3 for all strong digraphs D, and Ducoffe et al. proved that deciding whether a given digraph has proper connection number at most two is NP-complete. In this paper, we give a few classes of strong digraphs with proper connection number two, and from our proofs one can construct an optimal arc-coloring for a digraph of order n in time O ( n 3 ) .

The class of adjusted interval digraphs is a generalization of interval graphs. Although an O ( n 4 ) -time recognition algorithm is known (where n is the number of vertices of the graph), finding a more efficient algorithm remains an open question. This paper presents a new recognition algorithm with running time O ( n 3 ) . Adjusted interval digraphs are characterized by the existence of a min ordering and by the absence of invertible pairs. The proposed algorithm produces a min ordering if the given graph is an adjusted interval digraph; otherwise, it finds an invertible pair. As a byproduct, an alternative proof for the characterization is presented.

In this paper, the finite-time synchronization problem for multi-coupling fuzzy cellular neural networks (FCNNs) with stochastic perturbations and mixed delays is addressed. Compared with exponential synchronization and asymptotic synchronization in existing literature, finite-time synchronization of stochastic FCNNs is studied for the first time, which is of better significance. Combining graph-theoretical technique and Lyapunov method, under the framework of feedback control, some finite-time synchronization conditions are derived. Besides, from the perspective of the connectedness of FCNNs, we just demand at least one directed path on the digraph between different vertices in networks, instead of each sub-network. Then, the convergence time is explicitly proposed, which is connected with the parameters of control and topological structure of networks. Eventually, a numerical example is also carried out to demonstrate the practicability and validity of our proposed results. Furthermore, a secure communication synchronization problem is presented to illustrate the effectiveness of the obtained results.

Let D be a digraph with n vertices and σ 1 ( D ) ≥ σ 2 ( D ) ≥ ⋯ ≥ σ n ( D ) the singular values of the adjacency matrix A of D. The spectral norm of D is σ 1 ( D ) and the trace norm of D is ‖ D ‖ ⁎ = ∑ i = 1 n σ i ( D ) . In this paper we find lower bounds for the spectral norm of a digraph in terms of the structure of the digraph. Moreover, we introduce the concept of almost regular digraphs (extension of the well known almost regular graphs), and show that the lower bounds are attained precisely in almost regular digraphs. When we apply this theory to graphs, we recover well known lower bounds for the spectral radius of graphs. Also, we give a new upper bound for the trace norm of a digraph. Moreover, we determine the digraphs for which this bound is sharp: sink-source complete bipartite digraphs or symmetric balanced incomplete block designs (BIBD).

In this paper, two Brualdi-type eigenvalue inclusion sets are presented, which are characterized by the girth of the digraph associated with a tensor and are proved weaker than the conditions of Brualdi-type eigenvalue inclusion sets given by Bu et al. (2015) [7] . As applications of the above results, the conditions of nonsingularity and positive definiteness of tensors are given.

Seymour’s Second Neighborhood Conjecture states that every simple oriented graph has a vertex such that the cardinality of its second neighborhood is greater than or equal to the cardinality of its first neighborhood. The conjecture has been shown to hold for various families of digraphs but remains unsettled. A digraph is said to be k -antitransitive if any u to v path of length k implies there is no u to v edge. If the conjecture is shown to hold for k -antitransitive digraphs for an arbitrary k , this would settle it for finite digraphs, as every finite digraph is k -antitransitive for k greater than the length of its longest path. So far, the conjecture has been shown to hold for k -antitransitive simple oriented graphs for k ≤ 5 . In this paper we prove the conjecture for 6-antitransitive simple oriented graphs.

The leaderless, prescribed performance consensus problem for groups of agents with antagonistic interactions is addressed for the first time in this paper. We consider agents modeled by pure feedback nonlinear systems with unknown dynamics and an agent communication network described by a signed digraph with a directed spanning tree. A new proportional and integral (PI) variable transformation is proposed that enables the solution of the problem of leaderless bipartite consensus with prescribed performance by recasting it into a regulation problem with prescribed performance, which in turn we solve by a low complexity distributed control law. The algorithm guarantees uniform boundedness of all closed-loop signals and prescribed performance for the bipartite consensus error. Simulations verify the validity of our theoretical analysis.

In this paper we consider the digraph width measures directed path-width, directed tree-width, directed feedback vertex set number, directed feedback arc set number, cycle rank, DAG-depth, DAG-width and Kelly-width of recursively defined digraphs. While the minimization problem for these width measures is generally NP-hard, we prove that it is computable in linear time for all these parameters, except for Kelly-width, when restricted to directed co-graphs. As an important combinatorial tool, we show how these measures can be computed for the disjoint union, order composition, directed union, and series composition of two directed graphs, which further leads to some similarities. Although it is often not possible to compare them in general, we achieved a good comparison between the width measures within this framework. The equality of directed path-width and directed tree-width on directed co-graphs generalizes the known results for undirected co-graphs of Bodlaender and Mohring.

Many extension and generalization of fuzzy sets have been introduced and studied in the literature. Picture fuzzy set acquired more concentration in the domain of decision making, as many real time circumstances might have choices of more than one and researchers are looking for optimum choice/decision. Picture fuzzy digraph is a generalization of intuitionistic fuzzy set and fuzzy graph. In this paper, we redefine some preliminary operations of picture fuzzy graph and it is referred as picture fuzzy digraph (in short PFDG). We discuss some arithmetic operations and relations among PFDG. We further proposed a method to solve a shortest path problem using score function.

Every square matrix A = ( a u v ) ∈ C n × n can be represented as a digraph having n vertices. In the digraph, a block (or 2-connected component) is a maximally connected subdigraph that has no cut-vertex. The determinant and the permanent of a matrix can be calculated in terms of the determinant and the permanent of some specific induced subdigraphs of the blocks in the digraph. Interestingly, these induced subdigraphs are vertex-disjoint and they partition the digraph. Such partitions of the digraph are called the B -partitions. In this paper, first, we develop an algorithm to find the B -partitions. Next, we analyze the parameterized complexity of matrix determinant and permanent, where, the parameters are the sizes of blocks and the number of cut-vertices of the digraph. We give a class of combinations of cut-vertices and block sizes for which the parametrized complexities beat the state of art complexities of the determinant and the permanent.

This study introduces the decision-making trial and evaluation laboratory (DEMATEL) method to develop a causal relationship between factors of e-commerce. Differently from the typical correlation analysis which directly used two groups of variables to measure strength of correlation, this decision making approach develops two groups of factors which are known as cause and effect groups to enhance the significance of e-commerce. A survey approach was used to collect data from a purposeful sampling of undergraduate students at a public university in Malaysia. Empirical data were computed using the seven-step of DEMATEL method where the initial decision matrix was transformed to total relation matrix prior to developing cause and effect diagram. Not only did the DEMATEL unravel the relationship between factors, the DEMATEL method also provides degrees of importance of all factors. The main finding of this study is the visualization of the causal relationship among factors of e-commerce through a digraph, where the factor ‘information about products or services’ is mutually influenced by the factors ‘convenience’, ‘ease of use system’ and ‘web reputation’. E-commerce companies should, however, carefully evaluate the cause and effect factors, and the degree of importance of factors when offering services or products via online.

For a connected graph, it is known that there exists a partition of the vertex set into two dominating sets of the graph. However, for a digraph, there does not always exist such partition of the vertex set. We consider the problem of determining whether there is a partition of the vertex set into in- and out-dominating sets of the digraph. In this paper, we obtain the following results: (1) The decision problem is NP-complete even if a given digraph is acyclic, and (2) for an oriented tree, there is a polynomial time algorithm for deciding the existence of such partition.

k ≥ 2 be an integer. A digraph D = ( V , E ) is k -anti-transitive if for every pair of vertices u , v ∈ V , the existence of a directed path of length k from u to v implies that ( u , v ) ∉ E . Under this definition, digraphs without transitive triangles are 2-anti-transitive digraphs. In this paper, we prove that Seymour’s Second Neighborhood Conjecture (SSNC) holds for 5-anti-transitive oriented graphs and, as a consequence, it holds for every oriented graph whose underlining graph contains no cycle of length 6. SSNC asserts that every oriented finite simple graph has a vertex whose second out-neighborhood is at least as large as its first out-neighborhood.

In this paper, we introduce the concept of b -branchings in digraphs, which is a generalization of branchings serving as a counterpart of b -matchings. Here b is a positive integer vector on the vertex set of a digraph D , and a b -branching is defined as a common independent set of two matroids defined by b : an arc set is a b -branching if it has, for every vertex v of D , at most b ( v ) arcs entering v , and it is an independent set of a certain sparsity matroid defined by b and D . We demonstrate that b -branchings yield an appropriate generalization of branchings by extending several classic results on branchings. We first present a multi-phase greedy algorithm for finding a maximum-weight b -branching. We then prove a packing theorem extending Edmonds’ disjoint branchings theorem, and provide a strongly polynomial algorithm for finding optimal disjoint b -branchings. As a consequence of the packing theorem, we prove the integer decomposition property of the b -branching polytope. Finally, we deal with a further generalization in which a matroid constraint is imposed on the b ( v ) arcs sharing the terminal vertex v .

The study investigates bipartite synchronization of inertial coupled delayed neural networks (ICDNNs) with signed digraph by non-reduced order method and pinning control. The second-order CDNNs will not be converted into a first-order differential system by introducing variable substitution. Instead, a novel Lyapunov–Krasovskii functional is proposed which depends on the topology of the ICDNNs. Some sufficient conditions for linear matrix inequalities (LMI) are derived to realize bipartite synchronization, which is based on matrix decomposition theory and Barbalat Lemma in strongly connected signed networks. And then, M-matrix theory is utilized to generalize the results to networks containing directed spanning trees. Finally, two examples are used to verify the validity of the derived theoretical results.

Existence of a perfect matching in a random bipartite digraph with bipartition ( V 1 , V 2 ) , | V i | = n , is studied. The graph is generated in two rounds of random selections of a potential matching partner such that the average number of selections made by each vertex overall is below 2. More precisely, in the first round each vertex chooses a potential mate uniformly at random, and independently of all vertices. Given a fixed integer m, a vertex is classified as unpopular if it has been chosen by at most m vertices from the other side. Each unpopular vertex makes yet another uniform/independent selection of a potential mate. The expected number of selections made by a generic vertex v, i.e. its out-degree, is asymptotic to 1 + P ( Poisson ( 1 ) ≤ m ) ∈ ( 1 , 2 ) . Aided by Matlab software, we prove that for m = 1 , whence for all m ≥ 1 , the resulting bipartite graph has a perfect matching a.a.s. (asymptotically almost surely). On the other hand, for m = 0 a.a.s. a perfect matching does not exist. For the non-bipartite version of this model with vertex set [ n ] we show that already for m = 0 a.a.s. there exists a partial matching which leaves unmatched a O ( log − 1 ⁡ n ) fraction of vertices.

Fractional-order delayed multi-agent systems (FDMASs) in Riemann–Liouville sense are considered, where the corresponding topology is a weighted digraph. A new method is adopted to analyze consensus and some algebraic criteria are provided by applying classical Lyapunov direct method and algebraic graph theory. The main merit of our proposed approach is that the first-order derivative of the corresponding Lyapunov function can be taken. Two illustrative examples are provided to further show the validity of our approach.

In this paper, the distributed constrained optimization problem over a directed graph is considered. We assume that the digraph has a row-stochastic adjacency matrix, which corresponds to the case when agents assign weights to the received information individually. We present an algorithm that converges to the optimal solution even with a time-varying stepsize which is not attenuated to zero. The choice of stepsizes is relatively easy. The usable type of stepsizes is added. The diminishing or constant stepsizes can be used in our algorithm. Equality constraints and set constraints are also considered in this paper. Convergence analysis of the proposed algorithm relies on a conversion theorem between column-stochastic and row-stochastic matrices. Finally, the results of the numerical simulation are provided to verify the effectiveness of the proposed algorithm.

This paper investigates the leader-following bipartite consensus problem for second-order multi-agent systems with nonlinear dynamics, node-delay and signed digraph topology. By using pinning control strategies, an event-triggered controller is designed to achieve bipartite consensus in multi-agent systems, where a novel event-triggered function is proposed. Two cases are discussed in this paper according to whether the node-delay is differentiable or not. When the node-delay is differentiable, an LMI (Linear Matrix Inequality) condition is derived for reaching bipartite consensus in multi-agent systems by using M-matrix theory. When the node-delay is non-differentiable, some bipartite consensus conditions are developed based on Jensen inequality and the reciprocally convex approach. Moreover, it is shown that Zeno-behavior can be avoided for the designed event-triggered controller. Finally, some numerical examples are provided to illustrate the effectiveness and correctness of the theoretical analysis.

We study representations of a Leavitt path algebra $L$ of a finitely separated digraph $\Gamma$ over a field. We show that the category of $L$-modules is equivalent to a full subcategory of quiver representations. When $\Gamma$ is a (non-separated) row-finite digraph we determine all possible finite dimensional quotients of $L$ after giving a necessary and sufficient graph theoretic criterion for the existence of a nonzero finite dimensional quotient. This criterion is also equivalent to $L$ having UGN (Unbounded Generating Number) as well as being algebraically amenable. We also realize the category of $L$-modules as a retract, hence a quotient by an explicit Serre subcategory of the category of quiver representations (that is, $\mathbb{F}\Gamma$-modules) via a new colimit model for $M\otimes_{\mathbb{F}\Gamma} L$., Comment: 32 pages

A directed graph game consists of a cooperative game with transferable utility and a digraph which describes limited cooperation and the dominance relation among the players. Under the assumption that only coalitions of strongly connected players are able to fully cooperate, we introduce the digraph-restricted game in which a non-strongly connected coalition can only realize the sum of the worths of its strong components. The Myerson value for directed graph games is defined as the Shapley value of the digraph-restricted game. We establish axiomatic characterizations of the Myerson value for directed graph games by strong component efficiency and either fairness or bi-fairness.

The rank of a digraph is defined as the rank of its adjacency matrix. In this paper we show how to find all digraphs of rank k from the reduced bipartite graphs of rank 2k. In particular, since the bipartite graphs of rank 2 , 4 and 6 are known, then we characterize digraphs of rank 1 , 2 and 3. The results are based on rank-preserving operations on digraphs such as splitting and fusion of vertices or twin-deletion and vertex-multiplication.

In this paper, the finite-time consensus tracking control for multi-agent systems under Euler digraph and switching topology are discussed. The new nonlinear distributed control protocol is proposed under which the systems can reach finite-time consensus tracking. Furthermore, the leader needs to connect with only one follower and which agent is connected will have no effect on finite-time consensus under Euler digraph. It is found that adding edges or increasing feedback gains will be an effective way to reduce the settling time. Two sufficient conditions are proposed to achieve finite-time consensus tracking for multi-agent systems under Euler digraph and switching topology. Finally, numerical simulations are presented to verify the effectiveness of obtained theoretical results.

We study the distributed average consensus problem in multi-agent systems with directed communication links that are subject to quantized information flow. The goal of distributed average consensus is for the nodes, each associated with some initial value, to obtain the average (or some value close to the average) of these initial values. In this paper, we present and analyze a distributed averaging algorithm which operates exclusively with quantized values (specifically, the information stored, processed and exchanged between neighboring agents is subject to deterministic uniform quantization) and rely on event-driven updates (e.g., to reduce energy consumption, communication bandwidth, network congestion, and/or processor usage). We characterize the properties of the proposed distributed averaging protocol, illustrate its operation with an example, and show that its execution, on any timeinvariant and strongly connected digraph, will allow all agents to reach, in finite time, a common consensus value that is equal to the quantized average. We conclude with comparisons against existing quantized average consensus algorithms that illustrate the performance and potential advantages of the proposed algorithm., arXiv admin note: substantial text overlap with arXiv:1806.08535

In this paper it is proved that a networked discrete-time switching system, equipped with a given switches digraph, is input-to-state stable, provided that there exist multiple Lyapunov functions (one for each mode) for each subsystem in the network, satisfying suitable standard inequalities, and provided that a set of suitable vector small-gain conditions are satisfied. The small-gain theorem here provided for the input-to-state stability takes into account the switches digraph. That is, the less is the number of edges in the switches digraph, the less is the number of involved Lyapunov inequalities and small-gain conditions which, if satisfied, guarantee the input-to-state stability of the entire switching system under study. The multiple Lyapunov functions for the entire system, guaranteeing the input-to-state stability, are determined by the multiple Lyapunov functions for each subsystem in the family. To the author’s best knowledge, this is the first paper in the literature concerning small-gain theorems for the input-to-state stability of nonlinear discrete-time switching systems with given switches digraphs.

We study Susceptible-Infected-Recovered (SIR) epidemic model under mobility on multi-layer networks. We consider a scenario in which each individual within the population belong to one of the multiple classes and the population is distributed over multiple environmental patches. Individuals within a patch interact according to the SIR epidemic model and move across patches according to a class-dependent continuous time Markov chain. This yields a multi-layer network in which each layer is associated with a class and the connectivity in each layer corresponds to the digraph and transition rates of the associated Markov chain. For this multi-layer SIR model, we establish stability properties of equilibria using Lyapunov techniques, and derive simple conditions for the epidemic outbreak.

In this paper, the bipartite state synchronization problem of heterogeneous multi-agent systems (MASs) with active leader under adversarial signals over signed digraph is studied. The non-zero control of active leader is bounded, and we can update this control to protect followers from possible danger. Firstly, the bipartite state synchronization problem over signed digraph is converted to a regular tracking synchronization problem over nonnegative digraph after state transformations for heterogeneous MASs with active leader under adversarial signals. Then, novel distributed observers are designed to estimate the state of leader, as well as prevent disrupted data of agent from propagating the communication networks. Observer-based H∞ optimal controllers are also designed for each follower to mitigate effects on disrupted agents that agents under attack, and the inhomogeneous algebraic Riccati equations (AREs) are obtained. Meanwhile, a data-based off-policy reinforcement learning (RL) algorithm is used to solve the AREs without requiring the dynamics of agents. At last, the effectiveness of the algorithm is demonstrated by a simulation example.

Distributed control offers practical trade-off between globally (plant-wide) valid, computationally expensive centralized and locally effective decentralized architectures. While the development of distributed control theory (algorithms, stability, convergence properties, etc.) has made a significant progress in the last decade, decomposition of a system into an optimal distributed structure (classification of controller variables) has received considerably less attention. This paper focuses on achieving such a decomposition for integrated process systems with the objective of maximizing the strength of input–output impact and thus reducing the strength of inter-controller interactions. A graph-theoretic framework is used to abstract input-state-output dependence of a dynamical system and control-relevant interactions are quantified using weighted digraphs. It is shown that community detection in this weighted digraph is equivalent to distributed structure corresponding to strong input–output impact (quantified through the corresponding gain). Two relevant example systems are considered to illustrate the proposed framework and it is shown that the optimal distributed architectures adhere to the underlying structure of strong and weak inter-variable interactions.

An antimagic labeling of a digraph D with n vertices and m arcs is a bijection from the set of arcs of D to { 1 , 2 , … , m } such that all n oriented vertex sums are pairwise distinct, where an oriented vertex sum of a vertex is the sum of labels of all arcs entering that vertex minus the sum of labels of all arcs leaving it. Hefetz, Mutze and Schwartz conjectured every connected undirected graph admits an antimagic orientation. In this paper, we support this conjecture by proving that every Halin graph admits an antimagic orientation.

For an arc-colored digraph D, we say D is properly strongly connected, if for any ordered pair of vertices (x, y), D contains a directed path from x to y such that any adjacent arcs in that path have distinct colors. The directed proper connection number p c → ( D ) of a digraph D, is the minimum number of colors to make D properly strongly connected. Let D(n, p) denote the random digraph model, in which every arc of a digraph is chosen with probability p independently from other arcs. We prove that if p = { log n + log log n + λ ( n ) } / n , then with high probability, p c → ( D ( n , p ) ) = 2 , where λ(n) tends to infinite.

In this paper, we first give a multiset version of the graph-theoretical interpretation of the classic determinant of a matrix A based on a multiset generalization of the cycle cover of its associated digraph D ( A ) . Then, as a direct consequence of this interpretation, we present another algebraic proof of a weighted version of the original coin arrangements lemma.

Let k be an integer, k ≥ 2 , and let D = ( V , A ) be a digraph. We say that a subset S of V is a k-kernel if it is k-independent (the distance between any pair of vertices of S is at least k) and ( k − 1 ) -absorbent (the distance from any vertex in V ∖ S to S is at most k − 1 ); a 2-kernel is a kernel. A digraph is cyclically k-partite if it is homomorphic to a directed cycle of length k. It is well known that bipartite digraphs have a kernel, and it was recently proved that it is NP -complete to determine whether a cyclically 3-partite digraph has a 3-kernel. We prove that determining whether a cyclically k-partite digraph has a k-kernel is NP -complete for any integer k, k ≥ 4 , even for digraphs with circumference 2k. We also provide a new sufficient condition for a cyclically k-partite digraph to have a k-kernel, and discuss related open problems.

Let G ‾ n , k denote the set of strongly connected digraphs with order n and arc connectivity k, and let G ‾ n , k ⁎ denote the set of digraphs in G ‾ n , k with all vertices having outdegree and indegree greater than k. In this paper, we determine the unique digraph with the maximum signless Laplacian spectral radius among all digraphs in G ‾ n , k . We also determine the unique one with the maximum signless Laplacian spectral radius among all digraphs in G ‾ n , k ⁎ with k = 1 , 2 . For the general case, we propose a conjecture on the maximum signless Laplacian spectral radius among all digraphs in G ‾ n , k ⁎ . Moreover, we characterize the extremal digraph achieving the minimum distance signless Laplacian spectral radius among all digraphs in G ‾ n , k . We also characterize the extremal digraph achieving the minimum distance signless Laplacian spectral radius among all digraphs in G ‾ n , k ⁎ with k = 1 , 2 . For the general case, we propose a conjecture on the minimum distance signless Laplacian spectral radius among all digraphs in G ‾ n , k ⁎ .

Let D be an oriented graph, i.e., a digraph in which all arcs are not symmetric, with vertex set { 1 , … , n } . The adjacency matrix A = ( a i j ) of D is the n × n matrix defined as a i j = 1 if ij is an arc of D and a i j = 0 if ij is not an arc of D. The rank of D is defined to be the rank of its adjacency matrix. In this paper, oriented graphs of rank 2 are characterized.

In this paper, two singular value inclusion sets for rectangular tensors via a digraph and a lifting square tensor are given, respectively. Furthermore, it is shown that these two singular value inclusion sets are both tighter than the known result given by Zhao and Li in Theorem 2.1 of [25] , and singular value inclusion sets via a digraph in special case are tighter than the inclusion sets via a lifting square tensor, numerical examples are still given to show the relation among the inclusion sets via a digraph, the inclusion sets via a lifting square tensor and the known result given by Zhao and Li [25] . Finally, by using the lifting square tensors, the result of tensors provided by Bu et al. [24] is extended to rectangular tensors.