On isomorphism classes of generalized Fibonacci cubes

DOI10.1016/J.EJC.2015.05.011zbMATH Open1321.05160arXiv1402.6377OpenAlexW1016694222MaRDI QIDQ499490FDOQ499490

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)

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.

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

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)\)

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)

Cites Work

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

Cited In (14)

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

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)