گراف تسلط كلمات دودويي

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