Previous issue ·  Next issue ·  Recently posted articles ·  Most recent issue · All issues   
Home Overview Authors Editorial Contact Subscribe

Journal of the Ramanujan Mathematical Society

Volume 36, Issue 4, December 2021  pp. 309–323.

One-to-one conditional path covers on augmented cubes

Authors:  S. A. Kandekar, S. A. Mane and B. N. Waphare
Author institution:Center for Advanced Studies in Mathematics, Department of Mathematics, Savitribai Phule Pune University, Pune 411 007, India

Summary:  It is well known that the hypercube Q{n} is one of the most popular interconnection networks because~of its noteworthy properties such as maximum connectivity and effective routing algorithms. The augmented cube AQ{n}, is proposed by Choudam and Sunitha [5] as an improvement over the hypercube Q{n}, which owns more desirable properties than the hypercube, besides keeping some beneficial properties of Q{n}. This paper deals with the well-established problem of handling the maximum possible number of one-to-one communication requests without using a single node more than once and keeping required pair/pairs of vertices on different paths in augmented cubes. A major goal in the design of a system is to improve efficiency and fault-tolerant capacity. These systems are made fault-tolerant and efficient by providing redundant or spare processors. By keeping two or more active or non compatible processors on different paths, we can make these systems more efficient. Thus, we strengthen the parallel path result. The problem under study is to find the values of l and k such that for any (l + 2) vertices u, v and w{1}, w{2}, …, w{l} of AQ{n}, with each w{i} ∈ {u{c}, v{c}}, there exists t disjoint path cover between u and v for 2 ≤ t ≤ k in which w{i} and w{i}{c} lie on different path. In this paper, we solve the above problem for l = 1, k = 2n-1 and l = (2{n} - 4)/2, k = 2. i.e. we show that for 2 ≤ t ≤ (2n-1) and given any three distinct vertices u, v and w of AQ{n}, there exists t disjoint path cover (t-DPC) between u and v such that the given vertex w and its complement always lie on different paths. Also given any two vertices u and v, there exist disjoint path cover (2-DPC) between u and v such that for every pair w and w^c other than {u, u{c}, v, v{c}}, w and w{c} lie on different paths. In the first result we obtained, the value of k is optimal and in the second result, the value of l is optimal. Thus, to increase the efficiency and fault-tolerant capacity of the system, the requirement of two processors to be always on two different paths is fulfilled by the result proved in this paper.

Contents   Full-Text PDF