Skip to main content
SUPERVISOR
Ramin Gavadi jourtani,Behnaz Omoomi
رامین جوادی جورتانی (استاد مشاور) بهناز عمومی (استاد راهنما)
 
STUDENT
Alireza Sadeghpour
علیرضا صادق پور

FACULTY - DEPARTMENT

دانشکده ریاضی
DEGREE
Master of Science (MSc)
YEAR
1390

TITLE

A Characterization of Claw-Free Graphs
For more than one hundred years, the development of graph theory was been iired and guided mainly by the Four-Color Conjecture. The resolution of the conjecture by K. Appel and W. Haken in 1976 as well as the scientific and creative endeavors made by Erd?s, Tutte, and Berge marked a turning point in its history. Since then, this theory not only has experienced an explosive growth regarding both pure and applied subjects, but also has made a significant contribution towards development of other fields such as the Modern Applied Mathematics, Combinatorial Optimization, and Computer Science. Moreover, in a world where communication is of a prime importance, the versatility of graphs makes them indispensable tools in the design and analysis of communication networks. Particularly, recognition of the specific graphs' structure is a branch of graph theory by which graph theorists have been enthralled. In this dissertation, an attempt is made in order to describe the structure of claw-free graphs based upon a series of seven extraordinary papers together with their survey, all of which written by P. Seymour and M. Chudnovsky. A graph is called claw-free if no vertex has three pairwise nonadjacent neighbors. At first sight, there seem to be a great variety of types of claw-free graphs. For instance, there are line graphs , the graph of the icosahedron , complements of triangle-free graphs , and the Schl?fli graph (an amazingly highly-symmetric graph with 27 vertices). One of the other sub In addition to aforementioned claw-free graphs, prismatic graphs, a generalization of triangle-free graphs, whose complements are claw-free, defined as those graphs such as G in which for every triangle T of G, every vertex not in T has a unique neighbor in T. Prismatic graphs, playing an important role in describing claw-free graphs, can be characterized comprehensively. There are several other examples of claw-free graphs , regarded as "basic" claw-free graphs . Nevertheless , it is possible to prove a complete structure theorem for claw-free graphs . In fact, it is shown that every connected claw-free graph is obtained from one of the basic claw-free graphs by simple expansion operations . In this thesis, the precise statement of this structure theorem is explained, the proof is sketched, and a few applications about chromatic number of claw-free graphs are given. The chromatic number ?(G) of a graph G is the smallest number k for which the vertices of G can be colored in a way that no two adjacent vertices are assigned the same color. We are able to find some bounds for chromatic number of claw-free graphs through the structure theorem. Furthermore, a graph G is called perfect if ?(H)=?(H) for every induced subgraph H of G. We also give a full description of claw-free perfect graphs and similarly, claw-free b-perfect graphs, a Finally, a lot of these concepts and theorems can be extended to trigraphs, an extension of graphs with three kinds of adjacencies, strongly adjacent, strongly antiadjacent, and semiadjacent with the proviso that for every vertex v, there is at most one vertex u such that u is semiadjacent to v.
یک گراف را بدون پنجه گوییم هرگاه دارای رأسی نباشد که دارای سه همسایه‌ی دو به دو نامجاور باشد. در نگاه اوّل، این طور به نظر می‌رسد که انواع بسیار زیادی از گراف‌های بدون پنجه وجود دارد. به عنوان مثال، گراف‌های یالی، گراف بیست وجهی، مکمل گراف‌های منشوروار و گراف اشلفلی (یک گراف بسیار متقارن زیبا با ?? رأس) را می‌توان به عنوان نمونه‌هایی از گراف‌های بدون پنجه نام برد. به علاوه، اگر رئوس یک گراف را روی یک دایره مرتّب کنیم، سپس تعدادی بازه روی دایره انتخاب کرده و رئوس داخل بازه‌ها را به یک‌دیگر متّصل کنیم؛ گرافی که از این روش به ‌دست می‌آید، بدون پنجه است. مثال‌های بسیار زیاد دیگری مانند گراف‌های گفته شده وجود دارند که به عنوان گراف‌های بدون پنجه‌ی «اولیّه» در نظر گرفته می‌شوند. در واقع، این امکان وجود دارد که بتوان یک قضیه‌ی ساختاری برای گراف‌های بدون پنجه ارائه کرد. سیمور و چادنووسکی در یک سری از هفت مقاله ثابت کرده‌اند که هر گراف بدون پنجه را می‌توان از یکی از گراف‌های بدون پنجه‌ی اولیّه و با استفاده از اعمال گسترشی ساده به‌دست آورد. در این پایان‌نامه، گراف‌های بدون پنجه را بررسی کرده، صورت دقیق قضیه‌ی رده‌بندی گراف‌های بدون پنجه و شمایی از اثبات آن را بیان خواهیم کرد. در آخر سعی می‌کنیم با استفاده از قضیه‌ی ساختاری ذکر شده، در مورد عدد رنگی گراف‌های بدون پنجه، نتایجی را ارائه دهیم.

ارتقاء امنیت وب با وف بومی