Abstract
In this article the parameter matrices are enumerated of all perfect 2-colorings of the Johnson graphs J(8, 3) and J(8, 4), and several constructions are presented for perfect 2-coloring of J(2w, w) and J(2m, 3). The concept of a perfect coloring generalizes the concept of completely regular code introduced by P. Delsarte. The problem of existence of similar structures in Johnson graphs is closely related to the problem of existence of completely regular codes in Johnson graphs and, in particular, to the Delsarte conjecture on the nonexistence of nontrivial perfect codes in Johnson graphs, the problem of existence of block designs, and other well-known problems
چکیده
در این مقاله، ماتریسهای پارامتری همه دورنگ آمیزیهای تام گرافهای جانسون J(8,3) و J(8,4) نشان داده میشوند و ترکیبات متعدد برای دورنگ آمیزی تام J(2w,w) و J(2m,3) ارائه میشوند. مفهوم رنگ آمیزی تام، تعمیم مفهوم کد کاملاً منتظم است که توسط پی. دلسارته توسعه یافته است. مسئله وجود ساختارهای مشابه در گرافهای جانسون، اساساً با مسئله وجود کدهای کاملاً منتظم در گرافهای جانسون (و به طور خاص حدس دلسارته درباره عدم وجود کدهای تام غیربدیهی در گرافهای جانسون)، مسئله وجود طرحهای بلوکی و دیگر مسائل شناخته شده ارتباط مییابد.
-1مقدمه
اجازه دهید ابتدا تعاریف و مفاهیم لازم را ارائه کنیم. گردایه بردارهای دوتایی با طول n را با En نشان میدهیم. تعداد مختصاتهای غیرصفر x را، «وزن بردار x در En » مینامیم. مجموعه رئوس یک گراف جانسون J(n,w) به صورت گردایه همه بردارها در En با وزن w تعریف میشود؛ مجموعه یالهای این گراف، شامل زوج بردارهایی است که دقیقاً در دو مختصات با هم تفاوت دارند. به آسانی میتوان اثبات کرد که J(n,w) یک گراف منتظم از درجه w(n-w) و قطر w است. تعداد یالهای J(n,w) در کوتاه ترین مسیری که یک زوج از رئوس را به هم متصل میکند، فاصله جانسون نامیده میشود. توجه کنید که J(n, n-w) با J(n,w) یک ریخت است؛ بنابراین، بدون از دست دادن عمومیت، ما میتوانیم گرافهای جانسون J(n,w) را با شرط 2w≤n در نظربگیریم…