On isomorphism classes of generalized Fibonacci cubes

DOI10.1016/J.EJC.2015.05.011MaRDI QIDQ499490zbMATH OpenOpenAlexFDO

Authors Jernej Azarija, Sandi Klavžar, Jaehun Lee, Jay Pantone, Yoomi Rho

Publication date 30 September 2015

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

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

zbMATH Keywords

autocorrelation polynomial associated to a binary string

Mathematics Subject Classification ID

Pattern recognition, speech recognition (68T10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Abstract: The generalized Fibonacci cube $Q_d(f)$ is the subgraph of the $d$-cube $Q_d$ induced on the set of all strings of length $d$ that do not contain $f$ as a substring. It is proved that if $Q_d(f)cong{Q}_d(f^{\prime })$ then $|f|=|f^{\prime }|$. The key tool to prove this result is a result of Guibas and Odlyzko about the autocorrelation polynomial associated to a binary string. It is also proved that there exist pairs of strings $f,f^{\prime }$ such that $Q_d(f)cong{Q}_d(f^{\prime })$, where $|f|gefrac23(d+1)$ and $f^{\prime }$ cannot be obtained from $f$ by its reversal or binary complementation. Strings $f$ and $f^{\prime }$ with $|f|=|f^{\prime }|=d-1$ for which $Q_d(f)cong{Q}_d(f^{\prime })$ are characterized.

Recommendations

• Generalized Fibonacci cubes
• Proofs of two conjectures on generalized Fibonacci cubes
• Cube-complements of generalized Fibonacci cubes
• The self-concatenation of isometric strings is isometric
• Linear recognition of generalized Fibonacci cubes \(Q_h(111)\)

Cites work

• scientific article; zbMATH DE number 1157214 (Why is no real title available?)
• Analytic combinatorics
• Asymptotic number of isometric generalized Fibonacci cubes
• Asymptotic properties of Fibonacci cubes and Lucas cubes
• Connectivity of Fibonacci cubes, Lucas cubes, and generalized cubes
• Fast recognition of Fibonacci cubes
• Generalized Fibonacci cubes
• Generalized fibonacci cubes are mostly hamiltonian
• Linear recognition and embedding of Fibonacci cubes
• Parity index of binary words and powers of prime words
• Solution to a conjecture on words that are bad and 2-isometric
• String overlaps, pattern matching, and nontransitive games
• Structure of Fibonacci cubes: a survey
• The index of a binary word

Cited in

(15)

• Circular embeddability of isometric words
• Proofs of two conjectures on generalized Fibonacci cubes
• Asymptotic number of isometric generalized Fibonacci cubes
• Hypercubes and isometric words based on swap and mismatch distance
• On generalized Fibonacci cubes and unitary transforms
• Combinatorial isomorphism between Fibonacci classes
• Infinite families of 2-isometric and not 3-isometric binary words
• A negative answer to a problem on generalized Fibonacci cubes
• Cube-complements of generalized Fibonacci cubes
• A characterization of non-isometric binary words
• Quaternary \(n\)-cubes and isometric words
• The self-concatenation of isometric strings is isometric
• On \(k\)-ary \(n\)-cubes and isometric words
• All good (bad) words consisting of 5 blocks
• Proof of a conjecture on 2-isometric words

Describes a project that uses

Uses Software

• SageMath

This page was built for publication: On isomorphism classes of generalized Fibonacci cubes

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