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

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

کلیدواژه ها:

گراف تسلط کلمات دودویی ، قطر ، کمر ، شعاع ، عدد رنگی ، عدد استقلال