VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • On the mutually independent Hamiltonian cycles in faulty hypercubes
    Vukašinović, Vida ; Gregor, Petr ; Škrekovski, Riste
    Two ordered Hamiltonian paths in the n-dimensional hypercube ▫$Q_n$▫ are said to be independent if ▫$i$▫-th vertices of the paths are distinct for every ▫$1 \leq i \leq 2^n$▫. Similarly, two ... ▫$s$▫-starting Hamiltonian cycles are independent if the ▫$i$▫-th vertices of the cycle are distinct for every ▫$2 \leq i \leq 2^n$▫. A set ▫$S$▫ of Hamiltonian paths (▫$s$▫-starting Hamiltonian cycles) are mutually independent if every two paths (cycles, respectively) from ▫$S$▫ are independent. We show that for ▫$n$▫ pairs of adjacent vertices ▫$w_i$▫ and ▫$b_i$▫, there are ▫$n$▫ mutually independent Hamiltonian paths with endvertices ▫$w_i$▫, ▫$b_i$▫ in ▫$Q_n$▫. We also show that ▫$Q_n$▫ contains ▫$n-f$▫ fault-free mutually independent ▫$s$▫-starting Hamiltonian cycles, for every set of ▫$f \leq n-2$▫ faulty edges in ▫$Q_n$▫ and every vertex ▫$s$▫. This improves previously known results on the numbers of mutually independent Hamiltonian paths and cycles in the hypercube with faulty edges.
    Vir: Information sciences. - ISSN 0020-0255 (Vol. 236, jul. 2013, str. 224-235)
    Vrsta gradiva - članek, sestavni del
    Leto - 2013
    Jezik - angleški
    COBISS.SI-ID - 26622247
    DOI

vir: Information sciences. - ISSN 0020-0255 (Vol. 236, jul. 2013, str. 224-235)
loading ...
loading ...
loading ...

Vnos na polico