The Hamiltonian property of consecutive-d digraphs

DOI10.1016/0895-7177(93)90253-UMaRDI QIDQ1310230zbMATH OpenOpenAlexFDO

Authors D. Frank Hsu, Frank K. Hwang, Du Ding-Zhu

Publication date 12 June 1994

Published in Mathematical and Computer Modelling (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0895-7177(93)90253-u

zbMATH Keywords

consecutive-\(d\) digraph

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45) Graph theory (including graph drawing) in computer science (68R10)

Review text

Let be \(G\) a consecutive-\(d\) digraph whose \(n\) nodes are labelled by the residues modulo \(n\) such that a link exists from \(i\) to \(j\) iff \(j \equiv q_ i+v\), \(q_ i+v+1,\dots, q_ i+ v+d-1\) (modulo \(n)\). The authors prove that \(G\) is Hamiltonian iff \(d \geq \text{gcd} (n,q) >1\) and that \(G\) is Hamiltonian if \(\text{gcd} (n,q)=1\) for all \(d \geq 5\). This extends the characterisation of Hamiltonian consecutive--1 digraphs of \textit{F. K. Hwang} [Oper. Res. Lett. 6, No. 3, 125-127 (1987; Zbl 0615.05033)].

Recommendations

• scientific article; zbMATH DE number 4204369
• The Hamiltonian property of the consecutive-3 digraphs
• On connectivity of consecutive-d digraphs
• scientific article; zbMATH DE number 1286212
• Connectivity of consecutive-d digraphs

Cites work

• A Design for Directed Graphs with Minimum Diameter
• Connectivity of circulant digraphs
• Design to Minimize Diameter on Building-Block Network
• Generalized de Bruijn digraphs
• The Hamiltonian property of generalized de Bruijn digraphs
• The Hamiltonian property of linear functions

Cited in

(28)

• The Hamiltonian property of generalized de Bruijn digraphs
• A solution to a colouring problem of P. Erdős
• Connectivity of consecutive-d digraphs
• The Hamiltonian property of the consecutive-3 digraphs
• Super line-connectivity of consecutive-\(d\) digraphs
• Broadcasting and gossiping on de Bruijn, shuffle-exchange and similar networks
• An approach to solving \(A^{k}=J-I\)
• The Hamiltonian property of linear functions
• The complexity of finding fair independent sets in cycles
• Hamiltonian problems in directed graphs with simple row patterns
• Cooperative colorings and independent systems of representatives
• An algorithm for identifying cycle-plus-triangles graphs
• Hamiltonicity of large generalized de Bruijn cycles
• On endo-Cayley digraphs: the Hamiltonian property
• On 3-stage Clos networks with different nonblocking requirements on two types of calls
• Miscellaneous digraph classes
• scientific article; zbMATH DE number 4204369 (Why is no real title available?)
• scientific article; zbMATH DE number 3926956 (Why is no real title available?)
• scientific article; zbMATH DE number 1286212 (Why is no real title available?)
• Fair representation by independent sets
• scientific article; zbMATH DE number 828047 (Why is no real title available?)
• Eulerian and Hamiltonian dicycles in directed hypergraphs
• Strong coloring 2‐regular graphs: Cycle restrictions and partial colorings
• On finding constrained independent sets in cycles
• Partitioning into common independent sets via relaxing strongly base orderability
• Constructing graphs with no independent transversals
• A reduction of the ``cycles plus \(K_4\)'s problem
• The complexity of finding fair independent sets in cycles

This page was built for publication: The Hamiltonian property of consecutive-\(d\) digraphs

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