Embedding paths and cycles in 3-ary n-cubes with faulty nodes and links

The k-ary n-cube, denoted by , is one of the most important interconnection networks for parallel computing. In this paper, we consider the problem of embedding cycles and paths into faulty 3-ary n-cubes. Let F be a set of faulty nodes and/or edges, and n?2. We show that when |F|?2n-2, there exists a cycle of any length from 3 to in . We also prove that when |F|?2n-3, there exists a path of any length from 2n-1 to between two arbitrary nodes in . Since the k-ary n-cube is regular of degree 2n, the fault-tolerant degrees 2n-2 and 2n-3 are optimal.     

Edge-bipancyclicity of the k-ary n-cubes with faulty nodes and edges

The k-ary n-cube has been one of the most popular interconnection networks for massively parallel systems. In this paper, we investigate the edge-bipancyclicity of k-ary n-cubes with faulty nodes and edges. It is proved that every healthy edge of the faulty k-ary n-cube with f_v faulty nodes and f_e faulty edges lies in a fault-free cycle of every even length from 4 to kⁿ − 2f_v (resp. kⁿ − f_v) if k ? 4 is even (resp. k ? 3 is odd) and f_v + f_e ? 2n − 3. The results are optimal with respect to the number of node and edge faults tolerated.     

Augmented k-ary n-cubes

We define an interconnection network AQ_n,k which we call the augmented k-ary n-cube by extending a k-ary n-cube in a manner analogous to the existing extension of an n-dimensional hypercube to an n-dimensional augmented cube. We prove that the augmented k-ary n-cube AQ_n,k has a number of attractive properties (in the context of parallel computing). For example, we show that the augmented k-ary n-cube AQ_n,k: is a Cayley graph, and so is vertex-symmetric, but not edge-symmetric unless n = 2; has connectivity 4n − 2 and wide-diameter at most max{(n − 1)k − (n − 2), k + 7}; has diameter , when n = 2; and has diameter at most , for n ? 3 and k even, and at most , for n ? 3 and k odd.     

Hamiltonian circuit and linear array embeddings in faulty k-ary n-cubes

In this paper, we investigate the fault-tolerant capabilities of the k-ary n-cubes for even integer k with respect to the hamiltonian and hamiltonian-connected properties. The k-ary n-cube is a bipartite graph if and only if k is an even integer. Let F   be a faulty set with nodes and/or links, and let k?3$k?3$ be an odd integer. When |F|?2n-2$\left|F\right|?2n-2$, we show that there exists a hamiltonian cycle in a wounded k-ary n  -cube. In addition, when |F|?2n-3$\left|F\right|?2n-3$, we prove that, for two arbitrary nodes, there exists a hamiltonian path connecting these two nodes in a wounded k-ary n-cube. Since the k-ary n  -cube is regular of degree 2n$2n$, the degrees of fault-tolerance 2n-3$2n-3$ and 2n-2$2n-2$ respectively, are optimal in the worst case.     

Upper bounds on the queuenumber of k-ary n-cubes

A queue layout of a graph consists of a linear order of its vertices, and a partition of its edges into queues, such that no two edges in the same queue are nested. The minimum number of queues in a queue layout of a graph G, denoted by qn(G), is called the queuenumber of G. Heath and Rosenberg [SIAM J. Comput. 21 (1992) 927-958] showed that boolean n-cube (i.e., the n-dimensional hypercube) can be laid out using at most n−1 queues. Heath et al. [SIAM J. Discrete Math. 5 (1992) 398-412] showed that the ternary n-cube can be laid out using at most 2n−2 queues. Recently, Hasunuma and Hirota [Inform. Process. Lett. 104 (2007) 41-44] improved the upper bound on queuenumber to n−2 for hypercubes. In this paper, we deal with the upper bound on queuenumber of a wider class of graphs called k-ary n-cubes, which contains hypercubes and ternary n-cubes as subclasses. Our result improves the previous bound in the case of ternary n-cubes. Let denote the n-dimensional k-ary cube. This paper contributes three main results as follows:

(1)

if n?3.

(2)

if n?2 and 4?k?8.

(3)

if n?1 and k?9.

     

Hamiltonian paths and cycles with prescribed edges in the 3-ary n-cube

The k-ary n-cube has been one of the most popular interconnection networks for massively parallel systems. Given a set P of at most 2n − 2 (n ? 2) prescribed edges and two vertices u and v, we show that the 3-ary n-cube contains a Hamiltonian path between u and v passing through all edges of P if and only if the subgraph induced by P consists of pairwise vertex-disjoint paths, none of them having u or v as internal vertices or both of them as end-vertices. As an immediate result, the 3-ary n-cube contains a Hamiltonian cycle passing through a set P of at most 2n − 1 prescribed edges if and only if the subgraph induced by P consists of pairwise vertex-disjoint paths.     

Pancyclicity of ternary n-cube networks under the conditional fault model

A graph G is said to be conditional k-edge-fault pancyclic if after removing k faulty edges from G, under the assumption that each vertex is incident to at least two fault-free edges, the resulting graph contains a cycle of every length from its girth to |V(G)|. In this paper, we consider ternary n-cube networks and show that they are conditional (4n−5)-edge-fault pancyclic.     

Panconnectivity and edge-pancyclicity of 3-ary <Emphasis Type="Italic">N</Emphasis>-cubes

We study two topological properties of the 3-ary n-cube Q _n ³. Given two arbitrary distinct nodes x and y in Q _n ³, we prove that there exists an x–y path of every length ranging from d(x,y) to 3 ⁿ −1, where d(x,y) is the length of a shortest path between x and y. Based on this result, we prove that Q _n ³ is edge-pancyclic by showing that every edge in Q _n ³ lies on a cycle of every length ranging from 3 to 3 ⁿ .

Applications of interval valued t-norms (t-conorms) to fuzzy n-ary sub-hypergroups

In this paper, we study a generalization of group, hypergroup and n-ary group. Firstly, we define interval-valued fuzzy (anti fuzzy) n-ary sub-hypergroup with respect to a t-norm T (t-conorm S). We give a necessary and sufficient condition for, an interval-valued fuzzy subset to be an interval-valued fuzzy (anti fuzzy) n-ary sub-hypergroup with respect to a t-norm T (t-conorm S). Secondly, using the notion of image (anti image) and inverse image of a homomorphism, some new properties of interval-valued fuzzy (anti fuzzy) n-ary sub-hypergroup are obtained with respect to infinitely ∨-distributive t-norms T (∧-distributive t-conorms S). Also, we obtain some results of T-product (S-product) of the interval-valued fuzzy subsets for infinitely ∨-distributive t-norms T (∧-distributive t-conorms S). Lastly, we investigate some properties of interval-valued fuzzy subsets of the fundamental n-ary group with infinitely ∨-distributive t-norms T (∧-distributive t-conorms S).     

Atanassov’s intuitionistic (S, T)-fuzzy n-ary sub-hypergroups and their properties

In this paper, we define a new kind of intuitionistic fuzzy n-ary sub-hypergroups of an n-ary hypergroup. This definition, which is based on Atanassov’s intuitionistic fuzzy sets, t-norms and t-conorms, includes earlier definitions of (n-ary) sub-hypergroups, (intuitionistic) fuzzy (n-ary) sub-hypergroups. Then some related properties are investigated. Also, intuitionistic fuzzy relations with respect to t-norms and t-conorms on n-ary hypergroups are discussed.     

Constructing vertex-disjoint paths in (n, k)-star graphs

This work describes a novel routing algorithm for constructing a container of width n − 1 between a pair of vertices in an (n, k)-star graph with connectivity n − 1. Since Lin et al. [T.C. Lin, D.R. Duh, H.C. Cheng, Wide diameter of (n, k)-star networks, in: Proceedings of the International Conference on Computing, Communications and Control Technologies, vol. 5, 2004, pp. 160-165] already calculated the wide diameters in (n, n − 1)-star and (n, 1)-star graphs, this study only considers an (n, k)-star with 2 ? k ? n − 2. The length of the longest container among all constructed containers serves as the upper bound of the wide diameter of an (n, k)-star graph. The lower bound of the wide diameter of an (n, k)-star graph with 2 ? k ? ⌊n/2⌋ and the lower bound of the wide diameter of a regular graph with a connectivity of 2 or above are also computed. Measurement results indicate that the wide diameter of an (n, k)-star graph is its diameter plus 2 for 2 ? k ? ⌊n/2⌋, or its diameter plus a value between 1 and 2 for ⌊n/2⌋ + 1 ? k ? n − 2.     

On probabilistic n-ary hypergroups

The T-fuzzy n-ary subhypergroups of an n-ary hypergroup are defined by using triangular norms and some related properties are hence obtained. In particular, we consider the probabilistic version of n-ary hypergroups by using random sets and show that the fuzzy n-ary hypergroups defined by triangular norms are consequences of some probabilistic n-ary hypergroups under certain conditions. Some results on n-ary hypergroups recently given by Davvaz and Corsini are extended.     

Cycles passing through a prescribed path in a hypercube with faulty edges

Let Qn denote an n-dimensional hypercube with n?2, P be a path of length h in Qn and F⊂E(Qn)\E(P). Recently, Tsai proved that if 1?h?n−1 and |F|?n−1−h, then in the graph Qn−F the path P lies on a cycle of every even length from 2h+2 to n², and P also lies on a cycle of length 2h if |F|?h−2. In this paper, we show that if 1?h?2n−3 and |F|?n−2−⌊h/2⌋, then in Qn−F the path P lies on a cycle of every even length from 2h+2 to n², and P also lies on a cycle of length 2h if P contains two edges of the same dimension or P is a shortest path and |F∩E(Qh)|?h−2, where Qh is the h-dimensional subcube containing the path P. Moreover, the upper bound 2n−3 of h is sharp and the upper bound n−2−⌊h/2⌋ of |F| is sharp for any given h with 1?h?2n−3.     

Approximately n-secting an angle

It is a well-known fact that there exists an angle that cannot be trisected with a straightedge and a compass. In general, it is impossible to divide an arbitrary angle into n-angles equally with only a straightedge and a compass, where n is a positive integer. We give an efficient algorithm to divide an arbitrary angle into n-angles almost equally with only a straightedge and a compass. Using this method, we can construct an almost regular n-gon for arbitrary n.     

A (4n − 9)/3 diagnosis algorithm on n-dimensional cube network

As a generalization of the precise and pessimistic diagnosis strategies of system-level diagnosis of multicomputers, the t/k diagnosis strategy can significantly improve the self-diagnosing capability of a system at the expense of no more than k fault-free processors (nodes) being mistakenly diagnosed as faulty. In the case k ? 2, to our knowledge, there is no known t/k diagnosis algorithm for general diagnosable system or for any specific system. Hypercube is a popular topology for interconnecting processors of multicomputers. It is known that an n-dimensional cube is (4n − 9)/3-diagnosable. This paper addresses the (4n − 9)/3 diagnosis of n-dimensional cube. By exploring the relationship between a largest connected component of the 0-test subgraph of a faulty hypercube and the distribution of the faulty nodes over the network, the fault diagnosis of an n-dimensional cube can be reduced to those of two constituent (n − 1)-dimensional cubes. On this basis, a diagnosis algorithm is presented. Given that there are no more than 4n − 9 faulty nodes, this algorithm can isolate all faulty nodes to within a set in which at most three nodes are fault-free. The proposed algorithm can operate in O(N log₂ N) time, where N = 2ⁿ is the total number of nodes of the hypercube. The work of this paper provides insight into developing efficient t/k diagnosis algorithms for larger k value and for other types of interconnection networks.     

Strongly Hamiltonian laceability of the even k-ary n-cube

The interconnection network considered in this paper is the k-ary n-cube that is an attractive variance of the well-known hypercube. Many interconnection networks can be viewed as the subclasses of the k-ary n-cubes include the cycle, the torus and the hypercube. A bipartite graph is Hamiltonian laceable if there exists a Hamiltonian path joining every two vertices which are in distinct partite sets. A bipartite graph G is strongly Hamiltonian laceable if it is Hamiltonian laceable and there exists a path of length N − 2 joining each pair of vertices in the same partite set, where N = |V(G)|. We prove that the k-ary n-cube is strongly Hamiltonian laceable for k is even and n  2.     

On the k-tuple domination of de Bruijn and Kautz digraphs

In a digraph G, a vertex u is said to dominate itself and vertices v such that (u,v) is an arc of G. For a positive integer k, a k-tuple dominating set D of a digraph is a subset of vertices such that every vertex is dominated by at least k vertices in D. The k-tuple domination number of a given digraph is the minimum cardinality of a k-tuple dominating set of the digraph. In this letter, we give the exact values of the k-tuple domination number of de Bruijn and Kautz digraphs.     

On the k-tuple domination of generalized de Brujin and Kautz digraphs

A vertex u in a digraph G = (V, A) is said to dominate itself and vertices v such that (u, v) ∈ A. For a positive integer k, a k-tuple dominating set of G is a subset D of vertices such that every vertex in G is dominated by at least k vertices in D. The k-tuple domination number of G is the minimum cardinality of a k-tuple dominating set of G. This paper deals with the k-tuple domination problem on generalized de Bruijn and Kautz digraphs. We establish bounds on the k-tuple domination number for the generalized de Bruijn and Kautz digraphs and we obtain some conditions for the k-tuple domination number attaining the bounds.     

The m-pancycle-connectivity of a WK-Recursive network

In this paper, we study the m-pancycle-connectivity of a WK-Recursive network. We show that a WK-Recursive network with amplitude W and level L is strictly (5 × 2^L−1 − 2)-pancycle-connected for W ? 3. That is, each pair of vertices in a WK-recursive network with amplitude greater than or equal to 3 resides in a common cycle of every length ranging from 5 × 2^L−1 − 2 to N, where N is the size of the interconnection network; and the value 5 × 2^L−1 − 2 reaches the lower bound of the problem.