پژوهش های ریاضی، جلد ۸، شماره ۳، صفحات ۱۷۲-۱۷۹
عنوان فارسی بررسی وجود کد تام در مکعب لوکاس
چکیده فارسی مقاله مکعب لوکاس Λ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$.
کلیدواژه‌های انگلیسی مقاله Perfect code, Lucas cube, Fibonacci cube.
نویسندگان مقاله اعظم قلعه آقابابایی | Azam Ghaleh Agha Babai
University of Qom
دانشگاه قم

خدیجه فتحعلیخانی |


نشانی اینترنتی http://mmr.khu.ac.ir/browse.php?a_code=A-10-907-1&slc_lang=fa&sid=1
فایل مقاله فایلی برای مقاله ذخیره نشده است
کد مقاله (doi)
زبان مقاله منتشر شده fa
موضوعات مقاله منتشر شده جبر
نوع مقاله منتشر شده مقاله مستقل
برگشت به: صفحه اول پایگاه   |   نسخه مرتبط   |   نشریه مرتبط   |   فهرست نشریات