چکیده
یک K رنگ امیزی قوی یالی گراف G=(V,E) تابع K c:E است به طوری که به هردو یالی که منتهی به یک راس یا مجاور یک یال هستند مقدار ها (رنگ ها )متفاوتی اختصاص داده شود.اندیس رنگی قوی گراف G که ان را با G نشان می دهیم کوچکترین عددK است که یک –K رنگ امیزی قوی یالی برای G موجود می باشد در این پایان نامه G) )Xs را برای هالین گراف مکعبی کامل و گراف های دوبخشی Sm(k,1) وSm(k,1,) مورد مطالعه قرار می دهیم برولدی و کوبین حدسی ارایه دادند مبنی بر این که برای هر گراف دو بخشی G کران بالایی برای G) )Xs است که در ان ماکزیمم درجات در میان رئوس دو بخش گراف هستند.نکپرسیت درستی این حدس نشان داد.در این جا این حدس و اثبات نکپرسیت را بررسی می کنیم سپس کران ها ی بالایی برای اندیس رنگی قوی سه نوع حالت ضرب گراف ها بر حسب اندیس رنگی قوی هر کدام از گراف ها و به طور خاص اندیس رنگی قوی تورهای dبعدی برخی تورها چنبره ای و ابرمکعب های تعمیم یافته را بدست می اوریم رنگامیزی دیگری که در اینجا ان را مد نظر قرار می دهیم رنگ امیزی قوی یالی مجاورتی گراف است یک رنگ امیز ی قوی یالی مجاورتی گراف G یک رنگ امیزی یالی سره از گراف G است به طوری که مجموعه رنگ یال های منتهی به رئوس مجاور گراف مساوی نباشند کوچکترین عدد G را که با ان تعداد رنگ یک رنگ امیزی قوی یالی مجاورتی برای گراف G موجود باشد عدد رنگی قوی یالی مجاورتی گراف نامیده می شود.ژانگ و همکارانش مقدار G را برای برخی گراف های خاص به دست اوردند و نیز حدس زدند G +2 در این جا مطالعه این حدس پرداخته و ثابت می کنیم این حدس برای همه ی گراف های دو بخشی و گراف هایی که در انها G=3 برقرار می باشد.
کلمات کلیدی :گراف عدد رنگی اندیس رنگی قوی .عدد رنگی قوی یالی مجاورتی
فهرست مطالب
فصل اول تعاریف 1
1.1.مقدمه 2
2.1.گراف و زیر گراف 3
3.1.گراف های خاص 5
4.1.حاصل ضرب گراف ها 7
5.1.رنگ امیزی گراف ها 9
فصل دوم: رنگ امیزی قوی یالی گراف ها 12
1.2.مقدمه 13
2.2.اندیس رنگی قوی هالین گراف مکعبی کامل 16
3.2.اندیس رنگی قوی گراف های دو بخشی 28
1.3.2.اثبات حدس برولدی و کویین در حالت 2= 28
2.3.2.اندیس رنگی قوی در گراف های دو بخشی Sm(k,1) Sm(k,1) 33
4.2.اندیس رنگی قوی حاصل ضرب گراف ها 44
1.4.2.اندیس رنگی حاصل ضرب کارتزین گراف ها 45
2.4.2. اندیس رنگی حاصل ضرب کرونکر گراف ها 65
3.4.2. اندیس رنگی حاصل ضرب قوی گراف ها 69
فصل سوم:رنگ امیزی قوی یالی مجاورتی گراف ها 69
1.3.مقدمه 77
2.3.مقدار دقیق اندیس رنگی قوی مجاورتی برخی گراف ها 78
1.2.3.اندیس رنگی قوی مجاورتی درخت ها 80
2.2.3. اندیس رنگی قوی مجاورتی دورها 83
3.2.3. اندیس رنگی قوی مجاورتی گراف های دو بخشی کامل 87
4.2.3. اندیس رنگی قوی مجاورتی گراف های کامل 89
5.2.3. اندیس رنگی قوی مجاورتی گراف K(n,m) 93
3.3.اثبات حدس ژانگ و همکارانش برای گراف های با G=3 و فاقد یال تنها 108
4.3. اثبات حدس ژانگ و همکارانش برای گراف های دو بخشی فاقد یال تنها 128
فهرست منابع 140
فهرست جداول
1.3.مقادیر S به ازای مقادیر j,s 122
فهرست شکل ها
1.1.سه رنگ امیزی قوی ساز گار گراف C6 11
1.2. گراف H1 17
2.2. گراف H0 19
3.2.رنگ امیزی یالی قوی گراف H2 20
4.2. رنگ امیزی یالی گراف H3 20
5.2.زیر گراف S1 از Tn 21
6.2. زیر گراف S2 از Hn 24
7.2.دو زیر گراف S2,S2 در کنار هم 25
8.2.گراف Cn 50
9.2.دورنگ امیزی سازگار برای گراف P7,P5 59
1.3.گراف K(6,2) 93
2.3.گرافK(2,m) 94
3.3.مورد خاص G=K4 109
4.3.گراف H 112
5.3.موردی که x2,xj قطر H است 120
6.3.دنباله ی x0 ,x1,…,xn 126
7.3.مسیرهای x0yxn, yx0x 127
8.3.موردی که G یک پل دارد 127
9.3.اثباط شرایط 131
10.3.دوری به طول 2 به هنگ 4 دارای قطر 137
11.3.ستاره هایی از مولفه ها 138
2.3.مولفه مرکزی یک یال است 139

 


مقطع : کارشناسی ارشد

دانلود بخشی از درباره رنگ آميزی قوی يالی گراف ها

قبل از خرید فایل می توانید با پشتبانی سایت مشورت کنید