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
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.
Full Text: PDF PostScript