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

گراف تسلط کلمات دودویی، گرافی است جهت‌دار با مجموعه رئوس تمام کلمات دودویی به طول 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 هستند. در پایان، عدد استقلال این گراف نیز به روش‌ ترکیبیاتی محاسبه خواهد شد