### Connectivity of Fibonacci cubes, Lucas cubes, and generalized cubes

*Jernej Azarija, Sandi Klavžar, Jaehun Lee, Yoomi Rho*

#### Abstract

If f is a binary word and d a positive
integer, then the generalized Fibonacci cube
Q

_{d}(f) is the graph obtained from the d-cube Q_{d}by removing all the vertices that contain f as a factor, while the generalized Lucas cube Q_{d}(lucas(f)) is the graph obtained from Q_{d}by removing all the vertices that have a circulation containing f as a factor. The Fibonacci cube Γ_{d}and the Lucas cube Λ_{d}are the graphs Q_{d}(11) and Q_{d}(lucas(11)), respectively. It is proved that the connectivity and the edge-connectivity of Γ_{d}as well as of Λ_{d}are equal to ⌊ d+2 / 3⌋. Connected generalized Lucas cubes are characterized and generalized Fibonacci cubes are proved to be 2-connected. It is asked whether the connectivity equals minimum degree also for all generalized Fibonacci/Lucas cubes. It was checked by computer that the answer is positive for all f and all d≤9.Full Text: PDF PostScript