On diagnosability of large multiprocessor networks

We consider problems of fault diagnosis in multiprocessor systems. Preparata, Metze and Chien [F.P. Preparata, G. Metze, R.T. Chien, On the connection assignment problem of diagnosable systems, IEEE Trans. Comput. EC 16 (12) (1967) 848-854] introduced a graph theoretical model for system-level diagnosis, in which processors perform tests on one another via links in the system. Fault-free processors correctly identify the status of tested processors, while the faulty processors can give arbitrary test results. The goal is to identify faulty processors based on the test results. A system is said to be t-diagnosable if faulty units can be identified, provided the number of faulty units present does not exceed t. We explore here diagnosis problems for n-cube systems and give bounds for diagnosability of the n-cube. We also describe a simple diagnosis algorithm A which is linear in time and which can be used for sequential diagnosis as well as for incomplete diagnosis in one step. In particular, the algorithm applied to arbitrary topology based interconnection systems G with N processors improves previously known ones. It has sequential diagnosability , which is optimal in the worst case.     

Explicit solution of higher order boundary value regular differential systems avoiding the increase of the problem dimension

In this paper we obtain existence conditions and an expression of the general solution of higher order regular boundary value differential systems. The approach is based on the concept of co-solution of certain algebraic matrix equation and unlike to the classical approach we avoid the increase of the problem dimension derived from the consideration of an extended first order system.     

Families of regular solutions of singular systems

The seminal 1969 paper of W.A. Harris Jr., Y. Sibuya, and L. Weinberg provided new proofs for the Perron-Lettenmeyer theorem, as well as several other classical results, and has stimulated renewed consideration of families of regular solutions of certain singular problems. In this paper we give some further applications of the method developed there and, in addition, examine some connections between the Lettenmeyer theorem and an alternative theorem which addresses a problem posed by H.L. Turrittin that dates back to an 1845 example of Briot and Bouquet     

Gradient estimates of Poisson equations on Riemannian manifolds and applications

For the reflected diffusion generated by on a connected and complete Riemannian manifold M with empty or convex boundary, we establish some sharp estimates of sup_xM|G|(x) of the Poisson equation in terms of the dimension, the diameter and the lower bound of curvature. Applications to transportation-information inequality, to Cheeger's isoperimetric inequality and to Gaussian concentration inequality are given. Several examples are provided.     

Representation of infinite-dimensional neutral non-autonomous control systems

This paper studies the well-posedness of a class of non-autonomous neutral control systems in Banach spaces. We prove that such systems are represented by absolutely regular non-autonomous linear systems in the sense of Schnaubelt [R. Schnaubelt, Feedback for non-autonomous regular linear systems, SIAM J. Control Optim. 41 (2002) 1141-1165]. This paper can be considered as the non-autonomous version of the work presented in [H. Bounit, S. Hadd, Regular linear systems governed by neutral FDEs, J. Math. Anal. Appl. 320 (2006) 836-858].     

On the stability of the polygonal isoperimetric inequality

We obtain a sharp lower bound on the isoperimetric deficit of a general polygon in terms of the variance of its side lengths, the variance of its radii, and its deviation from being convex. Our technique involves a functional minimization problem on a suitably constructed compact manifold and is based on the spectral theory for circulant matrices.     

A family of regular graphs of girth 5

Murty [A generalization of the Hoffman-Singleton graph, Ars Combin. 7 (1979) 191-193.] constructed a family of (p^m+2)-regular graphs of girth five and order 2p^2m, where p?5 is a prime, which includes the Hoffman-Singleton graph [A.J. Hoffman, R.R. Singleton, On Moore graphs with diameters 2 and 3, IBM J. (1960) 497-504]. This construction gives an upper bound for the least number f(k) of vertices of a k-regular graph with girth 5. In this paper, we extend the Murty construction to k-regular graphs with girth 5, for each k. In particular, we obtain new upper bounds for f(k), k?16.     

The rotor-router model on regular trees

The rotor-router model is a deterministic analogue of random walk. It can be used to define a deterministic growth model analogous to internal DLA. We show that the set of occupied sites for this model on an infinite regular tree is a perfect ball whenever it can be, provided the initial rotor configuration is acyclic (that is, no two neighboring vertices have rotors pointing to one another). This is proved by defining the rotor-router group of a graph, which we show is isomorphic to the sandpile group. We also address the question of recurrence and transience: We give two rotor configurations on the infinite ternary tree, one for which chips exactly alternate escaping to infinity with returning to the origin, and one for which every chip returns to the origin. Further, we characterize the possible “escape sequences” for the ternary tree, that is, binary words a₁…an for which there exists a rotor configuration so that the kth chip escapes to infinity if and only if ak=1.     

An isoperimetric inequality in the optimization of circular rings under normal pressure

The problem of determining the optimal cross section of a circular ring so as to maximize the buckling pressure under a given total volume is formulated and solved. An isoperimetric inequality is proved: Among all the circular rings of given mass and radius, the ring with constant bending rigidity along the arc length has the largest critical buckling pressure.     

Eigenvalues and edge-connectivity of regular graphs

In this paper, we show that if the second largest eigenvalue of a d-regular graph is less than , then the graph is k-edge-connected. When k is 2 or 3, we prove stronger results. Let ρ(d) denote the largest root of x³-(d-3)x²-(3d-2)x-2=0. We show that if the second largest eigenvalue of a d-regular graph G is less than ρ(d), then G is 2-edge-connected and we prove that if the second largest eigenvalue of G is less than , then G is 3-edge-connected.     

The existence of even regular factors of regular graphs on the number of cut edges

For any even integer k and any integer i, we prove that a （kr ＋i）-regular multigraph contains a k-factor if it contains no more than kr - 3k/2＋ i ＋ 2 cut edges, and this result is the best possible to guarantee the existence of k-factor in terms of the number of cut edges. We further give a characterization for k-factor free regular graphs.     

Delay-independent stabilization of uncertain linear systems of neutral type

In this paper, we show that a sufficient condition for the delay-independent stabilizability of linear delay systems, which had been obtained by Amemiya et al., is also valid for linear neutral systems with measurable state variables by a new differential-difference inequality.The authors express their appreciation to Professor G. Leitmann for his useful comments.     

Connected domination of regular graphs

A dominating setD of a graph G is a subset of V(G) such that for every vertex v∈V(G), either v∈D or there exists a vertex u∈D that is adjacent to v in G. Dominating sets of small cardinality are of interest. A connected dominating setC of a graph G is a dominating set of G such that the subgraph induced by the vertices of C in G is connected. A weakly-connected dominating setW of a graph G is a dominating set of G such that the subgraph consisting of V(G) and all edges incident with vertices in W is connected. In this paper we present several algorithms for finding small connected dominating sets and small weakly-connected dominating sets of regular graphs. We analyse the average-case performance of these heuristics on random regular graphs using differential equations, thus giving upper bounds on the size of a smallest connected dominating set and the size of a smallest weakly-connected dominating set of random regular graphs.     

On estimating the regular normal cone to constraint systems and stationarity conditions

Estimating the regular normal cone to constraint systems plays an important role for the derivation of sharp necessary optimality conditions. We present two novel approaches and introduce a new stationarity concept which is stronger than M-stationarity. We apply our theory to three classes of mathematical programs frequently arising in the literature.     

Squares of regular languages

The square of a language L is the set of all words pp where p ∈ L. The square of a regular language may be regular too or context‐free or none of both. We give characterizations for each of these cases and show that it is decidable whether a regular language has one of these properties. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)