Perfect state transfer over interacting boson networks associated with group schemes

It is shown how to perfectly transfer an arbitrary qudit state in interacting boson networks. By defining a family of Hamiltonians related to Bose-Hubbard model, we describe a possible method for state transfer through bosonic atoms trapped in these networks with different kinds of coupling strengths between them. Particularly, by taking the underlying networks of so called group schemes as interacting boson networks, we show how choose suitable coupling strengths between the nodes, in order that an arbitrary qudit state be transferred from one node to its antipode, perfectly. In fact, by employing the group theory properties of these networks, an explicit formula for suitable coupling strengths has been given in order that perfect state transfer (PST) be achieved. Finally, as examples, PST on the underlying networks associated with cyclic group C _2m , dihedral group D _2n , Clifford group CL(n), and the groups U _6n and V _8n has been considered in details.     

Counting triangles in real-world networks using projections

Triangle counting is an important problem in graph mining. Two frequently used metrics in complex network analysis that require the count of triangles are the clustering coefficients and the transitivity ratio of the graph. Triangles have been used successfully in several real-world applications, such as detection of spamming activity, uncovering the hidden thematic structure of the web and link recommendation in online social networks. Furthermore, the count of triangles is a frequently used network statistic in exponential random graph models. However, counting the number of triangles in a graph is computationally expensive. In this paper, we propose the EigenTriangle and EigenTriangleLocal algorithms to estimate the number of triangles in a graph. The efficiency of our algorithms is based on the special spectral properties of real-world networks, which allow us to approximate accurately the number of triangles. We verify the efficacy of our method experimentally in almost 160 experiments using several Web Graphs, social, co-authorship, information, and Internet networks where we obtain significant speedups with respect to a straightforward triangle counting algorithm. Furthermore, we propose an algorithm based on Fast SVD which allows us to apply the core idea of the EigenTriangle algorithm on graphs which do not fit in the main memory. The main idea is a simple node-sampling process according to which node i is selected with probability \fracd_i2m{\frac{d_i}{2m}} where d _i is the degree of node i and m is the total number of edges in the graph. Our theoretical contributions also include a theorem that gives a closed formula for the number of triangles in Kronecker graphs, a model of networks which mimics several properties of real-world networks.     

Dual of a Complete Graph as an Interconnection Network

A new class of interconnection networks, the hypernetworks, has been proposed recently. Hypernetworks are characterized by hypergraphs. Compared with point-to-point networks, they allow for increased resource-sharing and communication bandwidth utilization, and they are especially suitable for optical interconnects. In this paper, we propose a scheme for deriving new hypernetworks using hypergraph duals. As an example, we investigate the dual, K*_n, of the n-vertex complete graph K_n and show that it has many desirable properties. We also present a set of fundamental data communication algorithms for K*_n. Our results indicate that the K*_n hypernetwork is a useful and promising interconnection structure for high-performance parallel and distributed computing systems.     

Hamiltonian connectivity and globally 3∗-connectivity of dual-cube extensive networks

In 2000, Li et al. introduced dual-cube networks, denoted by DC_n for n?1, using the hypercube family Q_n and showed the vertex symmetry and some fault-tolerant hamiltonian properties of DC_n. In this article, we introduce a new family of interconnection networks called dual-cube extensive networks, denoted by DCEN(G). Given any arbitrary graph G, DCEN(G) is generated from G using the similar structure of DC_n. We show that if G is a nonbipartite and hamiltonian connected graph, then DCEN(G) is hamiltonian connected. In addition, if G has the property that for any two distinct vertices u,v of G, there exist three disjoint paths between u and v such that these three paths span the graph G, then DCEN(G) preserves the same property. Furthermore, we prove that the similar results hold when G is a bipartite graph.     

Design and analysis of the rotational binary graph as an alternative to hypercube and Torus

Network cost is equal to degree?×?diameter and is one of the important measurements when evaluating graphs. Torus and hypercube are very well-known graphs. When these graphs expand, a Torus has an advantage in that its degree does not increase. A hypercube has a shorter diameter than that of other graphs, because when the graph expands, the diameter increases by 1. Hypercube Q_n has 2ⁿ nodes, and its diameter is n. We propose the rotational binary graph (RBG), which has the advantages of both hypercube and Torus. RBG_n has 2ⁿ nodes and a degree of 4. The diameter of RBG_n would be 1.5n?+?1. In this paper, we first examine the topology properties of RBG. Second, we construct a binary spanning tree in RBG. Third, we compare other graphs to RBG considering network cost specifically. Fourth, we suggest a broadcast algorithm with a time complexity of 2n???2. Finally, we prove that RBG_n embedded into hypercube Q_n results in dilation n, and expansion 1, and congestion 7.

     

The Complexity of the Kn,n-Problem for Node Replacement Graph Languages

The bounded K_n,n-problem is the question whether or not a graph language of a given graph grammar contains arbitrarily large complete bipartite subgraphs K_n,n. In this paper, we investigate the complexity of this problem for all relevant classes of node replacement graph grammers. Our main result states that the bounded K_n,n-problem is NL-complete for reduced nonblocking eNCE graph grammars and for reduced linear NCE graph grammars. As an application, our results settle the complexity of the problems whether or not the graph language of a given confluent, boundary, or linear graph grammar has bounded tree-width and whether or not it is an HR graph language.     

Edge-fault-tolerant bipancyclicity of Cayley graphs generated by transposition-generating trees

The Cayley graphs on the symmetric group plays an important role in the study of Cayley graphs as interconnection networks. Let Cay(S_n, B) be the Cayley graphs generated by transposition-generating trees. It is known that for any F?E(Cay(S_n, B)), if |F|≤n?3 and n≥4, then there exists a hamiltonian cycle in Cay(Sn, B)?F. In this paper, we show that Cay(S_n, B)?F is bipancyclic if Cay(S_n, B) is not a star graph, for n≥4 and |F|≤n?3.     

Which wheel graphs are determined by their Laplacian spectra?

The wheel graph, denoted by W_n+1, is the graph obtained from the circuit C_n with n vertices by adding a new vertex and joining it to every vertex of C_n. In this paper, the wheel graph W_n+1, except for W₇, is proved to be determined by its Laplacian spectrum, and a graph cospectral with the wheel graph W₇ is given.     

On equitable colouring of Knödel graphs

The notion of equitable colouring was introduced by Meyer in 1973. In this paper we find the equitable chromatic number χ₌ for the line graph of Knödel graphs L(W_{Δ, n}), central graph of Knödel graphs C(W_{Δ, n}) and corona graph of Knödel graphs W_{Δ, m}° W_{Δ, n}. As a by-product we obtain a new class of graphs that confirm Equitable Colouring Conjecture.     

The electrical resistance of a graph captures its commute and cover times

View ann-vertex,m-edge undirected graph as an electrical network with unit resistors as edges. We extend known relations between random walks and electrical networks by showing that resistance in this network is intimately connected with thelengths of random walks on the graph. For example, thecommute time between two verticess andt (the expected length of a random walk froms tot and back) is precisely characterized by the effective resistanceR _st betweens andt: commute time=2mR _st . As a corollary, thecover time (the expected length of a random walk visiting all vertices) is characterized by the maximum resistanceR in the graph to within a factor of logn:mR<-cover time<-O(mRlogn). For many graphs, the bounds on cover time obtained in this manner are better than those obtained from previous techniques such as the eigenvalues of the adjacency matrix. In particular, we improve known bounds on cover times for high-degree graphs and expanders, and give new proofs of known results for multi-dimensional meshes. Moreover, resistance seems to provide an intuitively appealing and tractable approach to these problems.     

Efficient Deadlock-Free Wormhole Routing and Virtual-Channel Reduction in Shuffle-Based Networks

Many aspects of shuffle-based networks have recently been studied by numerous researchers. However, no attention has been paid to deadlock-free wormhole routing algorithms. In this paper, for a set of shuffle-based networks, we introduce a graph-partitioning technique that enables a deadlock-free routing algorithm with fewer virtual channels than the known algorithms. This is achieved for the de Bruijn digraphs which are shown to require a maximum ofm− ⌊(m− 1)/r⌋ virtual channels per physical channel, wheremis the diameter andris the radix. Algorithms for the generalized de Bruijn graph, the de Bruijn Cube (dBCube) graph and the Shuffle–Exchange network are introduced, and virtual channel requirements are determined. The dBCube graph of size (r,N_b,n) requires a maximum ofm− ⌊(m− 1)/r⌋ virtual channels for the outcluster channels, and a maximum ofm+ 1 − ⌊m/r⌋ virtual channels for the incluster channels in most cases, wherem= ⌊log_rN_b⌋,ris the radix of a generalized de Bruijn graph of sizeN_b, andnrepresents the number of dimensions in a binary hypercube. We also show that a maximum ofm− ⌊(m− 1)/2⌋ virtual channels are required in shuffle-exchange networks with 2^mnodes.     

Component connectivity of the hypercubes

The r-component connectivity κ _r (G) of the non-complete graph G is the minimum number of vertices whose deletion results in a graph with at least r components. So, κ₂ is the usual connectivity. In this paper, we determine the r-component connectivity of the hypercube Q _n for r=2, 3, …, n+1, and we classify all the corresponding optimal solutions.     

Knowledge Representation

Abstract

In this semi-expository note, we first recall that every boolean function f of n variables is determined uniquely by a certain subset S of the nodes of the hypercube Q". We then propose the subgraph of Q_n induced by S as a realization of f, and call it the graph of a boolean function. We observe that boolean functions of the same type always have the same graph, but the converse does not hold. We conclude with the open question which suggests itself from a confrontation of the disjunctive and conjunctive normal forms of a boolean function.     

The twisted crossed cube

The topology of interconnection networks plays an important role in the performance of parallel and distributed computing systems. In this paper, we propose a new interconnection network called twisted crossed cube (TCQ_n) and investigate its basic network properties in terms of the regularity, connectivity, fault tolerance, recursiveness, hamiltonicity and ability to simulate other architectures, and so on. Then, we develop an effective routing algorithm Route (u, v) for TCQ_n that takes no more than d(u, v) + 1 steps for any two nodes (u, v) to communicate with each other, and the routing process shows that the diameter, wide diameter, and fault‐tolerant diameter of TCQ_n are about half of the corresponding diameters of the equivalent hypercube with the same dimension. In the end, by combining TCQ_n with crossed cube (CQ_n), we propose a preferable dynamic network structure, that is, the dynamic crossed cube, which has the same network diameter as TCQ_n/CQ_n and better properties in other respects, for example, its connection complexity is half of that of TCQ_n/CQ_n when the network scale is large enough, and the number of its average routing steps is also much smaller than that in TCQ_n/CQ_n. Copyright © 2015 John Wiley & Sons, Ltd.     

Aspects of neural modeling of multidimensional chaotic attractors

This article discusses various aspects of neural modeling of multidimensional chaotic attractors. The Lorenz and Rosler attractors are considered as representative cases and are thoroughly examined. These two dynamical systems are expressed, within acceptable accuracy limits, by the corresponding systems of difference equations. Initially, the complete neural models of the attractors are examined. In this case, the neural networks are supplied with the values X_n , Y_n , Z_n of the systems to predict all the next components (X_{n +1}, Y_{n +1}, and Z_{n +1}) of the attractors. In the second case, named ‘component simulation’, the neural models are trained to predict only one of the values X_n , Y_n , Z_n , when they are fed with the complete input vector as in the first case. In the third case, the proposed neural networks are trained to predict only one component (X_{n +1}, Y_{n +1}, or Z_{n +1}) of the attractors, given a number of past values of the same component. Finally, the ability of the networks to predict the Y and Z components of an X time series of the dynamical systems is examined. Since the response of some networks is not satisfactory, the distribution of absolute error is considered in order to form a realistic picture of the networks’ performance.     

Component connectivity of generalized Petersen graphs

Let G be a simple non-complete graph of order n. The r-component edge connectivity of G denoted as λ_r (G) is the minimum number of edges that must be removed from G in order to obtain a graph with (at least) r connected components. The concept of r-component edge connectivity generalizes that of edge connectivity by taking into account the number of components of the resulting graph. In this paper we establish bounds of the r component edge connectivity of an important family of interconnection network models, the generalized Petersen graphs GP(n, k) in which n and k are relatively prime integers.     

Memory-efficient algorithms for the verification of temporal properties

This article addresses the problem of designing memory-efficient algorithms for the verification of temporal properties of finite-state programs. Both the programs and their desired temporal properties are modeled as automata on infinite words (Büchi automata). Verification is then reduced to checking the emptiness of the automaton resulting from the product of the program and the property. This problem is usually solved by computing the strongly connected components of the graph representing the product automaton. Here, we present algorithms that solve the emptiness problem without explicitly constructing the strongly connected components of the product graph. By allowing the algorithms to err with some probability, we can implement them with a randomly accessed memory of size O(n) bits, where n is the number of states of the graph, instead of O(n log n) bits that the presently known algorithms require.     

Packet Routing and PRAM Emulation on Star Graphs and Leveled Networks

We consider the problem of permutation routing on a star graph, an interconnection network which has better properties than the hypercube. In particular, its degree and diameter are sublogarithmic in the network size. We present optimal randomized routing algorithms that run in O(D) steps (where D is the network diameter) for the worst-case input with high probability. We also show that for the n-way shuffle network with N = nⁿ nodes, there exists a randomized routing algorithm which runs in O(n) time with high probability. Another contribution of this paper is a universal randomized routing algorithm that could do optimal routing for a large class of networks (called leveled networks) which includes the star graph. The associative analysis is also network-independent. In addition, we present a deterministic routing algorithm, for the star graph, which is near optimal. All the algorithms we give are oblivious. As an application of our routing algorithms, we also show how to emulate a PRAM optimally on this class of networks.     

The rupture degree of trees

For the complete graph K _n , its rupture degree is defined as 1?n; and for a noncomplete connected graph G, its rupture degree is defined by r(G)=max{ω(G ? X)?|X|?m(G ? X):X ? V(G), ω(G ? X) > 1 }, where ω(G ? X) is the number of components of G ? X and m(G ? X) is the order of a largest component of G ? X. It is shown that this parameter can be well used to measure the vulnerability of networks. Li and Li proved in 2004 that computing the rupture degree for a general graph is NP-complete. In this paper, we give a recursive algorithm for computing the rupture degree of trees, and determine the maximum and minimum rupture degree of trees with given order and maximum degree.     

A Neural Algorithm for the Maximum Clique Problem: Analysis,Experiments, and Circuit Implementation

{In this paper we design and analyze a neural approximation algorithm for the Maximum Clique problem. This algorithm, having as input an arbitrary undirected graph G = \langle V, E\rangle , constructs a finite sequence of Hopfield networks such that the attractor of the last network in the sequence represents a maximal clique of G . We prove that D(G) ⋅ |E ^{\rm c} | , where D(G) = max _{{i,j}\notin E} \min{d _i , d _j } , d _i is the degree of the vertex i of G , and |E ^{\rm c} | denotes the cardinality of the set of edges in the complement graph, is an upper bound to the number of the networks in the sequence. Some experiments made on the second DIMACS benchmark and on random graphs show that: 1. The quality of the solutions found by the algorithm is satisfactory. 2. The theoretical upper bound D(G) ⋅ |E ^{\rm c} | is quite pessimistic. For random graphs we propose an empirical formula that gives a better estimate of the number of networks in the sequence. Moreover, thanks to the simplicity of the algorithm, we are able to design a uniform family of circuits of small size (\approx 10n ² log ₂ n ) that implements it. The circuit, which solves the problems for graphs of at most 32 vertices, has then been programmed on FPGAs (Field Programmable Gate Arrays). An analysis in terms of size and time complexity is given. Received November 10, 1998; revised December 2000.