Fault-Tolerant Embeddings of Hamiltonian Circuits in k-ary n-Cubes

DOI10.1137/S0895480196311183zbMath1018.68058MaRDI QIDQ4785687

Iain A. Stewart, Yaagoub A. Ashir

Publication date: 5 January 2003

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

embeddings; NP-completeness; fault-tolerance; Hamiltonian circuits; \(k\)-ary \(n\)-cubes

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C45: Eulerian and Hamiltonian graphs

Related Items

Edge-bipancyclicity in conditional edge-faulty k-ary n-cubes, Edge‐fault‐tolerant pancyclicity of alternating group graphs, Super Ck and Sub-Ck Connectivity of k-Ary n-Cube Networks, Conditional edge-fault Hamiltonian-connectivity of restricted hypercube-like networks, Fault-tolerant embedding of cycles of various lengths in \(k\)-ary \(n\)-cubes, Embedding long cycles in faulty \(k\)-ary \(2\)-cubes, Fault-tolerant Hamiltonian laceability of Cayley graphs generated by transposition trees, Hamiltonian paths and cycles with prescribed edges in the 3-ary \(n\)-cube, Matching preclusion for \(k\)-ary \(n\)-cubes, Augmented \(k\)-ary \(n\)-cubes, Conditional edge-fault-tolerant Hamiltonicity of dual-cubes, Panconnectivity and edge-pancyclicity of \(k\)-ary \(n\)-cubes with faulty elements, Hamiltonian cycles passing through linear forests in \(k\)-ary \(n\)-cubes, Embedding Hamiltonian paths in \(k\)-ary \(n\)-cubes with conditional edge faults, Fault tolerance in \(k\)-ary \(n\)-cube networks, Hamiltonian path embeddings in conditional faulty \(k\)-ary \(n\)-cubes, Pancyclicity of \(k\)-ary \(n\)-cube networks with faulty vertices and edges, The preclusion numbers and edge preclusion numbers in a class of Cayley graphs, Path embeddings in faulty 3-ary \(n\)-cubes, Embedding paths and cycles in 3-ary \(n\)-cubes with faulty nodes and links, Fault-free Hamiltonian cycles in twisted cubes with conditional link faults, Conditional fault Hamiltonicity of the complete graph, Fault-free longest paths in star networks with conditional link faults, Embedding Hamiltonian cycles in alternating group graphs under conditional fault model, Survey on path and cycle embedding in some networks, A type of perfect matchings extend to Hamiltonian cycles in \(k\)-ary \(n\)-cubes, The edge connectivity of expanded \(k\)-ary \(n\)-cubes, Hamiltonian cycles and paths in faulty twisted hypercubes, Pancyclicity of ternary \(n\)-cube networks under the conditional fault model, Edge-fault-tolerant Hamiltonicity of pancake graphs under the conditional fault model, Fault-tolerant pancyclicity of augmented cubes, Fault-free Hamilton cycles in burnt pancake graphs with conditional edge faults, Conditional edge-fault-tolerant edge-bipancyclicity of hypercubes, Fault-free Hamiltonian cycles in crossed cubes with conditional link faults, Panconnectivity and edge-pancyclicity ofk-aryn-cubes