Connectivity of Fibonacci cubes, Lucas cubes, and generalized cubesAzarija, Jernej (Avtor) Klavžar, Sandi (Avtor) Lee, Jaehun (Avtor) Rho, Yoomi (Avtor) Fibonacci cubeLucas cubegeneralized Fibonacci cubegeneralized Lucas cubeconnectivitycombinatorics on wordsIf ▫$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(\stackrel{\leftharpoondown}{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 ▫$\Gamma_d$▫ and the Lucas cube ▫$\Lambda_d$▫ are the graphs ▫$Q_d({11})$▫ and ▫$Q_d(\stackrel{\leftharpoondown}{11})$▫, respectively. It is proved that the connectivity and the edge-connectivity of ▫$\Gamma_d$▫ as well as of ▫$\Lambda_d$▫ are equal to ▫$\left\lfloor \frac{d+2}{3}\right\rfloor$▫. 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 \le9$▫.Discrete Mathematics & Theoretical Computer Science20152017-07-10 11:00:39Znanstveno delo66780ISSN: 1365-8050UDK: 519.17:004OceCobissID: 8089433COBISS_ID: 17220697ISSN pri članku: 1365-8050NUK URN: URN:SI:UM:DK:0XCNAHN9sl