Jernej Azarija ; Sandi Klavžar ; Jaehun Lee ; Yoomi Rho - Connectivity of Fibonacci cubes, Lucas cubes and generalized cubes

dmtcs:2115 - Discrete Mathematics & Theoretical Computer Science, February 12, 2015, Vol. 17 no. 1 -
Connectivity of Fibonacci cubes, Lucas cubes and generalized cubesArticle

Authors: Jernej Azarija 1; Sandi Klavžar 2,3,1; Jaehun Lee 4; Yoomi Rho 4

  • 1 Institute of Mathematics, Physics and Mechanics [Ljubljana]
  • 2 Faculty of Mathematics and Physics [Ljubljana]
  • 3 Faculty of Natural Sciences and Mathematics [Maribor]
  • 4 Department of Mathematics [Incheon]

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.

Volume: Vol. 17 no. 1
Section: Graph Theory
Published on: February 12, 2015
Submitted on: October 1, 2014
Keywords: Fibonacci cube,Lucas cube,generalized Fibonacci cube,generalized Lucas cube,connectivity,combinatorics on words,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[INFO.INFO-HC] Computer Science [cs]/Human-Computer Interaction [cs.HC]

Consultation statistics

This page has been seen 430 times.
This article's PDF has been downloaded 480 times.