نام دانشجو: حسین اسماعیلیان

   استاد راهنمای اول: دکتر ابراهیم قربانی

   استاد ارزیاب داخلی: دکتر محمدجواد نیک مهر

   استاد ارزیاب داخلی: دکتر فرزانه رمضانی

   استاد ارزیاب خارجی: دکتر سعید اکبری

   استاد ارزیاب خارجی: دکتر نادر جعفری راد

 

 

فرض کنید ‎G یک گراف و ‎A(G) ‎ ماتریس مجاورت آن باشد. منظور از رتبه و -1‎رتبه گراف ‎G‎ به‌ترتیب رتبه ماتریس‌های A(G) و ‎A(G)+I است. گرافی که فاقد رأس ایزوله و فاقد دو رأس با همسایگی یکسان باشد کاهشی و گرافی که فاقد دو رأس با همسایگی بسته یکسان است، هم‌کاهشی نامیده می‌شود. گراف کاهشی ‎ Gرا ماکسیمال گویند هرگاه هر گراف کاهشی که ‎ Gرا به‌عنوان زیرگراف القایی دارد، رتبه بیشتری از رتبه G داشته باشد. یکی از اهداف این رساله ارائه نتایجی درمورد گراف‌های ماکسیمال است. درخت‌های ماکسیمال (یک درخت کاهشی، ماکسیمال است اگر زیردرخت سره‌ای از یک درخت کاهشی با همان رتبه نباشد) را رده‌بندی می‌کنیم. سپس رده‌بندی نسبتاً کاملی از گراف‌های دوستی تعمیم یافته ماکسیمال را ارائه می‌دهیم. هم‌چنین مسأله یافتن بیشترین مرتبه گراف‌های با 1-‎رتبه داده شده در بین گراف‌های هم‌کاهشی را بررسی می‌کنیم. بیشترین مرتبه درخت‌های کاهشی، گراف‌های دوبخشی، مکمل‌دوبخشی و مکمل درخت‌های با 1-‎رتبه داده شده و ساختار این گراف‌ها را تعیین می‌کنیم. مطالبی نیز پیرامون یک حدس در مورد گراف‌های کلی بیان می‌کنیم. مسأله لیتلوود-آفورد به تعداد ترکیب‌های خطی ساخته شد از مجموعه‌ای از بردارها می‌پردازد که در مجموعه‌ای محدب قرار می‌گیرند. ما نسخه‌ای گسسته از این مسأله را ارائه می‌دهیم و از آن برای مطالعه مسأله رتبه-مرتبه، که در فوق شرح داده شد، استفاده می‌کنیم. به‌ویژه، بیشترین مرتبه گراف‌های مکمل‌دوبخشی با 1-رتبه داده شده را تعیین می‌کنیم و اثبات جدیدی برای مسأله تعیین بیشترین رتبه گراف‌های دوبخشی کاهشی با ‌رتبه داده شده ارائه می‌دهیم. در نهایت بیشترین مرتبه گراف‌های فاقد مثلث با 1-رتبه داده شده را بررسی می‌کنیم.