عنوان پایان‌نامه
مسائلی درباره گرافها و درختان صحیح
- رشته تحصیلی
- ریاضی کاربردی
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس علوم شماره ثبت: 4733;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 52829
- تاریخ دفاع
- ۰۸ بهمن ۱۳۹۰
- دانشجو
- فاطمه شفیعی
- استاد راهنما
- مرتضی محمدنوری
- چکیده
- اگر ریشه‌های چند‌جمله‌ای مشخصه یک گراف صحیح باشند، آن گراف، گراف صحیح نامیده می‌شود. تاکنون روش‌های مختلفی برای ساختن گراف‌های صحیح و درختان صحیح ارائه شده است. اکثر خانواده‌های ساخته شده توسط این روش‌ها شامل دسته‌ای نامتناهی گراف (یا درخت ) هستند. مسأله وجود درختان صحیح با قطر به اندازه کافی بزرگ که مدتها به‌عنوان مسأله باز مطرح بود، یکی از مسایل مهم قابل اشاره در این زمینه است. در سال 2010 چیکواری با ارائه یک روش ساخت جالب و زیبا برای درختان صحیح با قطر زوج دلخواه، به سوال مذکور پاسخ مثبت داد. قابل ذکر است تمامی درختان صحیح شناخته شده قبل از کار چیکواری، دارای حداکثر قطر ده بودند. پس از آن با اندکی تغییر در روش ساخت چیکواری درختان صحیح با قطر فرد دلخواه ارائه شدند. در این رساله چندین روش ساخت برای گرافها و درختان بررسی می‌شود سپس در هر روش شرایط لازم و کافی برای صحیح بودن گراف‌های ساخته شده ارائه می‌شود. نهایتا روش چیکواری برای ساختن درختان صحیح مورد بحث قرار می‌گیرد.
- Abstract
- A graph is called integral if all roots of its characteristic polynomial are integers. Several different constructions for integral graphs and integral trees are given. Most of the obtained classes, contain infinitely many graphs ( or trees ). For a long time, it has been an open question whether there exist integral trees of any diameter d. Given a nice construction of integral trees of any even diameter, Csikv?ri answered this question affirmatively in 2010. It is remarkable that the largest diameter of known integral trees before Csikv?ri's work was d=10. Later by a slight modification of this construction, integral trees of any odd diameter were obtained. In this thesis some constructions of graphs and trees are reviewed. Then necessary and sufficient conditions for these graphs to be integral are given. Finally, we discuss Csikv?ri's construction of integral trees.
