عنوان پایان‌نامه
دسته بندی بعضی از گراف ها به کمک مکمل ستاره ها
- رشته تحصیلی
- ریاضی‌محض
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس علوم شماره ثبت: 3798;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 41372
- تاریخ دفاع
- ۲۱ دی ۱۳۸۷
- استاد راهنما
- حمید رضا میمنی
- دانشجو
- فاطمه سادات موحدی
- چکیده
- فرض کنید H یک گراف از مرتبه ی t که مقدار ویژه ی آن باشد. تکنیک مکمل ستاره روشی است برای ساختن گراف G،که H را به عنوان زیر گراف القایی داشته باشد و مقدار ویژه¬ی گراف از تکرر باشد. ( مرتبه¬ی گراف G است.)در این پایان نامه، ابتدا ویژگی کلی از مکمل ستاره در یک گراف را بیان می کنیم و سپس به بیان تکنیک مکمل ستاره می پردازیم. ثابت شده است برای ، است و بنابراین تعداد متناهی گراف G با،وجود دارد. همچنین به کمک مکمل ستاره و توابع پیوسته درجه ی دوم، یک کران بالا برای مرتبه ی یک گراف با یک فضای ویژه از هم بعد معین، ارائه می دهیم. به ویژه نشان خواهیم داد که برای گراف های منظم G، این کران یک واحد تقلیل می یابد، و این کران برای یک گراف منظم G بدست می آید اگر و فقط اگر G، گراف قویا منظم بحرانی باشد. کلمات کلیدی: مجموعه ی مکمل ستاره، تکنیک مکمل ستاره، مقدار ویژه، گراف قویا منظم.
- Abstract
- The star complement technique Let H be a graph of order t with no eigenvalue is a method to construct a graph G with H as on induced subgraph and having as an eigenvalue of multiplicity equal to n-t .( n, the order of G ). H is said to be a . star complement for G and At first, in this thesis, we study some general properties of star complement for G. and also we investigate the star complement technique. , and therefore then,Another main result asserts that if, t. we also study star complements there are a finite number of graph G and and associated quadratic functions are used to obtain a sharp upper bound for the order of a graph with an eigenvalue of prescribed codimention. In this direction, we show that for regular graphs the bound can be reduced by 1, and that this reduced is attained by a regular graph G if and if G is an extremal strongly regular graph. Key Word: star complement, the star complement technique, eigenvalue, strongly regular graph.
