Skip to Main content Skip to Navigation
Journal articles

Connectivity of Fibonacci cubes, Lucas cubes and generalized cubes

Abstract : If f is a binary word and d a positive integer, then the generalized Fibonacci cube Qd(f) is the graph obtained from the d-cube Qd by removing all the vertices that contain f as a factor, while the generalized Lucas cube Qd(lucas(f)) is the graph obtained from Qd 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 Qd(11) and Qd(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.
Complete list of metadata

Cited literature [25 references]  Display  Hide  Download

https://hal.inria.fr/hal-01196859
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Thursday, September 10, 2015 - 3:17:22 PM
Last modification on : Friday, March 15, 2019 - 4:55:06 PM
Long-term archiving on: : Tuesday, December 29, 2015 - 12:02:17 AM

File

dmtcs-17-1-5.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

Jernej Azarija, Sandi Klavžar, Jaehun Lee, yoomi Rho. Connectivity of Fibonacci cubes, Lucas cubes and generalized cubes. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2015, Vol. 17 no. 1 (1), pp.79--88. ⟨10.46298/dmtcs.2115⟩. ⟨hal-01196859⟩

Share

Metrics

Record views

120

Files downloads

782