21745 articles – 15574 Notices  [english version]

hal-00535686, version 2

On the domination number and the 2-packing number of Fibonacci cubes and Lucas cubes

Aline Castro () 1, Sandi Klavzar () 2, Michel Mollard () 1, Yoomi Rho () 3

Computers & Mathematics with Applications (2011) 2655-2660

Résumé : Let $\Gamma_n$ and $\Lambda_n$ be the $n$-dimensional Fibonacci cube and Lucas cube, respectively. The domination number $\gamma$ of Fibonacci cubes and Lucas cubes is studied. In particular it is proved that $\gamma(\Lambda_{n})$ is bounded below by $\left\lceil\frac{L_{n}-2n}{n-3}\right\rceil$, where $L_n$ is the $n$-th Lucas number. The 2-packing number $\rho$ of these cubes is also studied. It is proved that $\rho(\Gamma_{n})$ is bounded below by $2^{2^{\frac{\lfloor \lg n\rfloor}{2}-1}}$ and the exact values of $\rho(\Gamma_n)$ and $\rho(\Lambda_n)$ are obtained for $n\le 10$. It is also shown that ${\rm Aut}(\Gamma_n) \simeq \mathbb{Z}_2$.

  • 1 :  Institut Fourier (IF)
  • CNRS : UMR5582 – Université Joseph Fourier - Grenoble I
  • 2 :  Faculty of Mathematics and Physics [Ljubljana] (FMF)
  • University of Ljubljana
  • 3 :  Department of Mathematics
  • University of Incheon
  • Domaine : Mathématiques/Combinatoire
  • Mots-clés : Fibonacci cubes – Lucas cubes – Domination number – 2-packing number – Automorphism group – Computer search
  • Référence interne : IF_PREPUB
  • Versions disponibles :  v1 (14-11-2010) v2 (14-03-2011)
 
  • hal-00535686, version 2
  • http://hal.archives-ouvertes.fr/hal-00535686
  • oai:hal.archives-ouvertes.fr:hal-00535686
  • Contributeur : Michel Mollard <>
  • Soumis le : Lundi 14 Mars 2011, 13:37:06
  • Dernière modification le : Mardi 3 Janvier 2012, 14:17:24