Particular cycles of a binary de Bruijn digraph

DOI10.1016/J.EJC.2009.03.026MaRDI QIDQ966168zbMATH OpenOpenAlexFDO

Authors B. E. Eshmatov

Publication date 27 April 2010

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ejc.2009.03.026

zbMATH Keywords

binary de Bruijn digraphcycle

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38)

Review text

The authors investigate an isomorphism \(\sigma \) between a directed de Bruijn digraph \(B(2,n)\) and its converse, which is the digraph obtained from \(B(2,n)\) by reversing the direction of all its arcs. A cycle \(C\) is said to be \(\sigma \)-self-converse when the cycle \(\sigma (C)\) coincides with its converse. A characterization is determined of \(\sigma \)-self-converse cycles, distinguishing the cases of \(n\) even and odd. Moreover it is proved that, for \(n\) even, there does not exist a Hamiltonian \(\sigma \)-self-converse cycle, while, for \(n\) odd, we determine a constructive proof of the existence of a similar cycle. Finally they prove that for every \(n\) there exists only one \(\sigma \)-self-converse cycle of length 4.

Recommendations

• The Hamiltonian property of generalized de Bruijn digraphs
• Binary de Bruijn cycles under different equivalence relations
• scientific article; zbMATH DE number 167887
• Counting small cycles in generalized de Bruijn digraphs
• Generalized de Bruijn graphs

Cites work

• A note on recursive properties of the de Bruijn, Kautz and FFT digraphs
• Binary de Bruijn cycles under different equivalence relations
• On a Homomorphism of the de Bruijn Graph and its Applications to the Design of Feedback Shift Registers

Cited in

(5)

• A proof of Simmons' conjecture
• Constructing the minimum dominating sets of generalized de Bruijn digraphs
• A pretty, surprising, graph graft
• On the Sound Covering Cycle Problem in Paired de Bruijn Graphs
• Perfect matchings of a graph associated with a binary de Bruijn digraph

This page was built for publication: Particular cycles of a binary de Bruijn digraph

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