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