Average Convergence for Directed&Undirected Graphs in Distributed Systems

Consensus control of multi-agent systems is an innovative paradigm for the development of intelligent distributed systems.This has fascinated numerous scientific groups for their promising applications as they have the freedom to achieve their local and global goals and make their own decisions.Network communication topologies based on graph and matrix theory are widely used in a various real-time applications ranging from software agents to robotics.Therefore,while sustaining the significance of both directed and undirected graphs,this research emphases on the demonstration of a distributed average consensus algorithm.It uses the harmonic mean in the domain of multi-agent systems with directed and undirected graphs under static topologies based on a control input scheme.The proposed agreement protocol focuses on achieving a constant consensus on directional and undirected graphs using the exchange of information between neighbors to update their status values and to be able to calculate the total number of agents that contribute to the communication network at the same time.The proposed method is implemented for the identical networks that are considered under the directional and non-directional communication links.Two different scenarios are simulated and it is concluded that the undirected approach has an advantage over directed graph communication in terms of processing time and the total number of iterations required to achieve convergence.The same network parameters are introduced for both orientations of the communication graphs.In addition,the results of the simulation and the calculation of various matrices are provided at the end to validate the effectiveness of the proposed algorithm to achieve consensus.

The Determination of Optimal Routes of an Undirected Network

In this research paper, a routing problem of undirected networks has been solved. The problem was to determine the optimal routes of a telecommunication network. A heuristic approach has been adopted,due to the specific uature of the problem.The problem is only concerned withdistant(remote) nodes of the network which are indirectly linked through a single intermediate node.To determine the optimal routes,the devised heuristic has been coded in FORTRAN language. Forthe validation of developed heuristic,it has been implemented on two sample networks. Finally, ithas been applied to the actual(gived) network. The achieved results have proved its application insepcific networking problem. It can also enhance the effective utilization of available resources.

The Wiener Index of an Undirected Power Graph

The undirected power graph P(Zn) of a finite group Zn is the graph with vertex set G and two distinct vertices u and v are adjacent if and only if u ≠ v and or . The Wiener index W(P(Zn)) of an undirected power graph P(Zn) is defined to be sum of distances between all unordered pair of vertices in P(Zn). Similarly, the edge-Wiener index We(P(Zn)) of P(Zn) is defined to be the sum of distances between all unordered pairs of edges in P(Zn). In this paper, we concentrate on the wiener index of a power graph , P(Zpq) and P(Zp). Firstly, we obtain new results on the wiener index and edge-wiener index of power graph P(Zn), using m,n and Euler function. Also, we obtain an equivalence between the edge-wiener index and wiener index of a power graph of Zn.

Compression schemes for concept classes induced by three types of discrete undirected graphical models

Sample compression schemes were first proposed by Littlestone and Warmuth in 1986.Undi-rected graphical model is a powerful tool for classification in statistical learning.In this paper,we consider labelled compression schemes for concept classes induced by discrete undirected graphical models.For the undirected graph of two vertices with no edge,where one vertex takes two values and the other vertex can take any finite number of values,we propose an algorithm to establish a labelled compression scheme of size VC dimension of associated concept class.Further,we extend the result to other two types of undirected graphical models and show the existence of labelled compression schemes of size VC dimension for induced concept classes.The work of this paper makes a step forward in solving sample compression problem for concept class induced by a general discrete undirected graphical model.

A novel genetic algorithm based on all spanning trees of undirected graph for distribution network reconfiguration

Network reconfiguration is of theoretical and practical significance to guarantee safe and economical operation of distribution system.In this paper,based on all spanning trees of undirected graph,a novel genetic algorithm for electric distribution network reconfiguration is proposed.Above all,all spanning trees of simplified graph of distribution network are found.Tie branches are obtained with spanning tree subtracted from simplified graph.There is one and only one switch open on each tie branch.Decimal identity number of open switch on each tie branch is taken as the optimization variable.Therefore,the length of chromosome is very short.Each spanning tree corresponds to one subpopulation.Gene operations of each subpopulation are implemented with parallel computing method.Individuals of offspring after gene operation automatically meet with radial and connected constraints for distribution network operation.Disadvantages of conventional genetic algorithm for network reconfiguration that a large amount of unfeasible solutions are created after crossover and mutation,which result in very low searching efficiency,are completely overcome.High calculation speed and superior capability of the proposed method are validated by two test cases.

Domination Numbers of Undirected Toroidal Mesh

The （d, m）-domination number γd,m is a new measure to characterize the reliability of resources-sharing in fault tolerant networks, in some sense, which can more accurately characterize the reliability of networks than the m-diameter does. In this paper, we study the （d,4）-domination numbers of undirected toroidal mesh

ISOMORPHISM OF UNDIRECTED CIRCULANT GRAPHS

Let n>1 be an integer, N={1,2,… n-1}. Let K={k1,…, km}（?）N. A directed circulant graph Gn（K） is defined as follows. The vertex set is V={V0,V1,…, vn-1} and the edge set E={vivj|, there exists an integer t, 1≤t≤m, such that j- i≡kt （mod n）}. Gn（K）is an undirected circulant graph if k∈K implies n-k∈K. Let X and Y be two subsets of N. We call X and Y equivalent if there exists an

From undirected graphs to directed graphs:a new technique makes it possible for multi-agent systems

This communique introduces a simple technique,which enables the Laplacian-like matrix of a directed graph to be diagonalisable.Thus many results on multi-agent systems over undirected graphs can be extended to directed graphs.As an example,we show how to make this extension of a popular Automatica paper.

Adaptive Third-Order Leader-Following Consensus of Nonlinear Multi-agent Systems with Perturbations

We investigate the third-order leader-following consensus problem of nonlinear multi-agent systems in undirected network topologies.Based on graph theory and Lyapunov stability theory,the adaptive control method is employed to achieve leader-following consensus in an undirected network of agents with nonlinear third-order dynamics against the perturbations.Simulation examples validate the correctness of the results and show that the control gains have a great influence on the convergence performance of errors for a short time.

Push-Pull Finite-Time Convergence Distributed Optimization Algorithm

With the widespread application of distributed systems, many problems need to be solved urgently. How to design distributed optimization strategies has become a research hotspot. This article focuses on the solution rate of the distributed convex optimization algorithm. Each agent in the network has its own convex cost function. We consider a gradient-based distributed method and use a push-pull gradient algorithm to minimize the total cost function. Inspired by the current multi-agent consensus cooperation protocol for distributed convex optimization algorithm, a distributed convex optimization algorithm with finite time convergence is proposed and studied. In the end, based on a fixed undirected distributed network topology, a fast convergent distributed cooperative learning method based on a linear parameterized neural network is proposed, which is different from the existing distributed convex optimization algorithms that can achieve exponential convergence. The algorithm can achieve finite-time convergence. The convergence of the algorithm can be guaranteed by the Lyapunov method. The corresponding simulation examples also show the effectiveness of the algorithm intuitively. Compared with other algorithms, this algorithm is competitive.

Search for Directed Networks by Different Random Walk Strategies

A comparative study is carried out on the effciency of five different random walk strategies searching on directed networks constructed based on several typical complex networks.Due to the difference in search effciency of the strategies rooted in network clustering,the clustering coeFfcient in a random walker's eye on directed networks is defined and computed to be half of the corresponding undirected networks.The search processes are performed on the directed networks based on Erd(o)s-Rényi model,Watts-Strogatz model,Barabási-Albert model and clustered scale-free network model.It is found that self-avoiding random walk strategy is the best search strategy for such directed networks.Compared to unrestricted random walk strategy,path-iteration-avoiding random walks can also make the search process much more effcient.However,no-triangle-loop and no-quadrangle-loop random walks do not improve the search effciency as expected,which is different from those on undirected networks since the clustering coefficient of directed networks are smaller than that of undirected networks.

Improved Approximation of Layout Problems on Random Graphs

Inspired by previous work of Diaz, Petit, Serna, and Trevisan (Approximating layout problems on random graphs, Discrete Mathematics, 235, 2001, 245-253), we show that several well-known graph layout problems are approximable to within a factor arbitrarily close to 1 of the optimal with high probability for random graphs drawn from an Erdös-Renyi distribution with appropriate sparsity conditions using only elementary probabilistic analysis. Moreover, we show that the same results hold for the analogous problems on directed acyclic graphs.

A DIRECTED GRAPH ALGORITHM OF VARIATIONAL GEOMETRY BASED ON GEOMETRIC REASONING

The undirected graph to express engineering drawings is discussed .The principle to re-solve and reason the undirected graph is presented, and the algorithm finally transforms theundirected graph into the resolvable directed graph. Therefore,a rapid and simple way is suppliedfor variational design. A prototype of this algorithm has been implemented, and some examplesare given.

Enhancing Controllability Robustness of q-Snapback Networks through Redirecting Edges

Te well-known small-world network model was established by randomly rewiring edges,aiming to enhance the synchronizability of an undirected nearest-neighbor regular network.Tis paper demonstrates via extensive numerical simulations that randomly redirecting edges could enhance the robustness of the network controllability for directed snapback networks against both random and intentional node-removal and edge-removal attacks.

NEW SUFFICIENT CONDITIONS OF THE LONGEST CYCLES OF 1-TOUGH GRAPHS

In this letter all graphs will be finite, undirected simple graphs. Let G be a graph. We shall use V(G), E and c(G) to denote the vertex set, the edge set and the circumference of G respectively. We denote the distance between u and v by d(u, v). Let p=V(G).

ON THE CIRCUMFERENCES OF 1-TOUGH GRAPHS

A connected graph G is called t-tough if t · ω (G — S) ≤ | S| for any subset S of V(G) where t is a real number and ω(G—S) is the number of components of G- S. Obviously, a 1-tough graph is 2-connected. The circumference c(G) of graph G is the length of a longest cycle of G. There is an extensive literature

TWO EDGE-DISJOINT HAMILTONIAN CYCLES IN AN ORE-TYPE-(2), GRAPH

In this letter we consider only undirected simple graphs. Let G he a graph, we shall use V(G) and E(G) to denote the vertex set and the edge set of G respectively. And let u,v∈V(G), we denote the degree of v by d(u) and the edge joining u and v by uv.

GRAPH DECOMPOSITION WITH CONSTRAINT ON THE MINIMUM DEGREE

Ⅰ. BACKGROUND AND NOTATIONS In this paper all graphs will be finite, undirected, and have no loops or multiple edges, namely, simple graphs. E. Gyovi put the following question: Is there a (the smallest) natural number f(s,t) such that the vertex set of each graph of connectivity being f (s, t) at least has a decomposition into sets which would induce subgraphs of connectivity being

LONGEST CYCLES IN κ-CONNECTED K_(1,3)-FREE GRAPHS

In this letter all graphs will be finite, undirected simple graphs. Let G be a graph. we shall use V（G） and E（G） to denote the vertex set and the edge set of G respectively, and let p=, |V（G）|. Let UV（G）. We shall use G[U] to denote the subgraph induced by U. A graph G is K1, 3-free if G[U]K1, 3 for any UV（G）. A graph G is m-path-connected if there is a （u, v）-path of length at least m for any {u, v} V（G）.