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
• oai:hal.archives-ouvertes.fr:hal-00535686
• Contributeur :
• Soumis le : Lundi 14 Mars 2011, 13:37:06
• Dernière modification le : Mardi 3 Janvier 2012, 14:17:24