| HAL-Inria | Publications, software ... of Inria's scientists |
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.
Cited literature [25 references]
https://hal.inria.fr/hal-01196859
Contributor : Coordination Episciences Iam <>
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
Contributor : Coordination Episciences Iam <>
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