Unpaired Many-to-Many Disjoint Path Cover of Balanced Hypercubest

DOI10.1142/S0129054121500301MaRDI QIDQ6114850zbMATH OpenOpenAlexFDO

Authors Huazhong Lü, Tingzeng Wu

Publication date 15 August 2023

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1912.05443

zbMATH Keywords

balanced hypercubeinterconnection networkparallel computingunpairedvertex-disjoint path cover

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (including graph drawing) in computer science (68R10)

Abstract: The balanced hypercube $B{H}_n$, a variant of the hypercube, was proposed as a desired interconnection network topology. It is known that $B{H}_n$ is bipartite. Assume that $S=s_1,s_2,cdots,s_{2n-2}$ and $T=t_1,t_2,cdots,t_{2n-2}$ are any two sets of vertices in different partite sets of $B{H}_n$ ($ngeq2$). It has been proved that there exists paired 2-disjoint path cover of $B{H}_n$. In this paper, we prove that there exists unpaired $(2n-2)$-disjoint path cover of $B{H}_n$ ($ngeq2$) from $S$ to $T$, which improved some known results. The upper bound $2n-2$ of the number of disjoint paths in unpaired $(2n-2)$-disjoint path cover is best possible.

Recommendations

• Unpaired many-to-many disjoint path covers in restricted hypercube-like graphs
• Paired many-to-many disjoint path covers of the hypercubes
• Many-to-many \(n\)-disjoint path covers in \(n\)-dimensional hypercubes
• Paired many-to-many disjoint path covers in faulty hypercubes
• Many-to-many two-disjoint path covers in restricted hypercube-like graphs

Cites work

• Bipanconnectivity of balanced hypercubes
• Edge-fault-tolerant edge-bipancyclicity of balanced hypercubes
• Edge-pancyclicity and Hamiltonian laceability of the balanced hypercubes
• Fault-tolerant Hamiltonian laceability of balanced hypercubes
• Graph theory
• Hamiltonian connectivity of restricted hypercube-like networks under the conditional fault model
• Hamiltonian cycle embedding for fault tolerance in balanced hypercubes
• Hamiltonian laceability in hypercubes with faulty edges
• scientific article; zbMATH DE number 52113 (Why is no real title available?)
• Linear array and ring embeddings in conditional faulty hypercubes
• Many-to-Many Disjoint Path Covers in the Presence of Faulty Elements
• Matching preclusion for balanced hypercubes
• On extra connectivity and extra edge-connectivity of balanced hypercubes
• On Path Cover Problems in Digraphs and Applications to Program Testing
• Paired 2-disjoint path covers of faulty \(k\)-ary \(n\)-cubes
• Paired many-to-many disjoint path covers in faulty hypercubes
• Paired Many-to-Many Disjoint Path Covers in Recursive Circulants (G(2ᵐ,4))
• Parallel edge-region-based segmentation algorithm targeted at reconfigurable MultiRing network
• Super connectivity of balanced hypercubes
• Symmetric Property and Reliability of Balanced Hypercube
• The 1-fixed-endpoint path cover problem is Polynomial on interval graphs
• Two node-disjoint paths in balanced hypercubes
• Unpaired many-to-many disjoint path covers in restricted hypercube-like graphs

Cited in

(12)

• Many-to-many two-disjoint path covers in cylindrical and toroidal grids
• Two node-disjoint paths in balanced hypercubes
• Concentration behavior: 50 percent of \(h\)-extra edge connectivity of pentanary \(n\)-cube with exponential faulty edges
• Paired 3-Disjoint Path Covers in Bipartite Torus-Like Graphs with Edge Faults
• Embedded Edge-Connectivity Reliability Evaluation of Augmented Hypercube Interconnection Networks
• One-to-one disjoint-path covers of leaf-sort graphs
• Paired 2-disjoint path cover of burnt pancake graphs with n - 3 faulty elements
• Paired (n - 1)-to-(n - 1) disjoint path covers in bipartite transposition-like graphs
• Degree conditions for disjoint path covers in digraphs
• Many-to-many \(n\)-disjoint path covers in \(n\)-dimensional hypercubes
• Unpaired many-to-many disjoint path covers in restricted hypercube-like graphs
• Unpaired many-to-many vertex-disjoint path covers of a class of bipartite graphs

This page was built for publication: Unpaired Many-to-Many Disjoint Path Cover of Balanced Hypercubest

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6114850)