بررسی وجود کد تام در مکعب لوکاس

مکعب لوکاس λn گرافی است که مجموعه راس‌های آن همه رشته‌های دودویی به طول n است به‌طوری‌که این رشته‌ها دو 1 متوالی ندارند و مولفه ابتدایی و انتهایی آن‌ها هم‌زمان 1 نیستند. دو راس از این مجموعه را با یک یال به هم متصل می‌کنیم، هرگاه به‌طور دقیق در یک مولفه متفاوت باشند. همچنین یک کد تام از یک گراف زیرمجموعه‌ای از راس‌های گراف است به‌طوری‌که هر راس از گراف یا عضوی از مجموعه کد است و یا به‌طور دقیق با یک عضو از مجموعه کد مجاور است. در این مقاله نشان می‌دهیم که مکعب لوکاس λn تنها برای n≤3 کد تام دارد.

the (non-)existence of perfect codes in lucas cubes

a fibonacci string of length $n$ is a binary string $b = b_1b_2ldots b_n$ in which for every $1 leq i < n$, $b_icdot b_{i+1} = 0$. in other words, a fibonacci string is a binary string without 11 as a substring.similarly, a lucas string is a fibonacci string $b_1b_2ldots b_n$ that $b_1cdot b_n = 0$.for a natural number $ngeq1$, a fibonacci cube of dimension $n$ is denoted by $gamma_n$ and is defined as a graph whose vertices are  fibonacci strings of length $n$ such that two vertices $b_1b_2ldots b_n$ and $b’_1b’_2ldots b’_n$ are adjacent if $b_ineq b’_i$ holds for exactly one $iin{1,ldots, n}$.a lucas cube of  dimension $n$, $lambda_n$, is a subgraph of $gamma_n$ induced by the lucas strings of length $n$.let $g=(v,e)$ be a simple undirected graph. a perfect code is a subset $c$ of $v$ in such a way that for every $vin c$, the sets ${uin v | d(u, v) = 1}$ are pairwise disjoint and make a partition for $v$. in other words, each vertex of $g$ is either in $c$ or is adjacent to exactly one of the elements of $c$. it is proved that fibonacci cube $gamma_n$, admits a perfect code if and only if $nleq3$.in this paper, we prove the same result for lucas cubes i.e, $lambda_n$ admits a perfect code if and only if $nleq3$.