گراف تسلط کلمات دودویی

Abstract

گراف تسلط کلمات دودویی، گرافی است جهت‌دار با مجموعه رئوس تمام کلمات دودویی به طول n که با نماد (Γ_n ) ⃗ نشان داده می‌شود، برای هر رأس دلخواه w=w_1 w_2⋯w_n از آن قرار می‌دهیم B_1 (w)={1≤i≤n|w_i=1} و دو رأس v و w را با پیکان جهت‌دار v→w به هم وصل می‌کنیم هرگاه داشته باشیم B_1 (w)⊆B_1 (v). در این مقاله، به مطالعه و محاسبه برخی پارامترهای این گراف می‌پردازیم؛ به عنوان مثال، پس از محاسبه فاصله هر دو رأس و نیز انحراف از مرکز هر رأس، ثابت می‌شود که قطر گراف زمینه (Γ_n ) ⃗ برابر 3 و شعاع آن برابر 2 است. همچنین ثابت خواهد شد که این گراف دارای تعداد 〖 3〗^n-3(2^n-1)یال است. در ادامه نشان خواهیم داد که عدد خوشه‌ای و عدد رنگی رأسی گراف تسلط کلمات دودویی با طول n هردو برابر n-1 هستند. در دیگر نتایج، ثابت می‌شود که عدد رنگی یالی این گراف و ماکزیمم درجه رئوس آن مساوی 2^(n-1)-2 هستند. در پایان، عدد استقلال این گراف نیز به روش‌ ترکیبیاتی محاسبه خواهد شد