چکیده

یک –k رنگ آمیزی قوی یالی g(v,E)  تابع [K]  c:E است به طوری که به هر دو یالی که منتهی  یک راس یا مجاور با یکی سال هستند. مقدار ها (رنگ های) متفاوتی اختصاص داده می شود. اندیس رنگی قوی گراف G که آن را با X(s) نشان می دهیم کوچکترین عدد kاست که یک –K رنگ آمیزی قوی یالی برای G موجود باشد. در این پایان نامه X(s) را برای هالین گراف مکعبی کامل و گراف های دو بخشی sm(k,l) مورد مطالعه قرار می دهیم. برولدی و کوبین حدسی ارایه دادند مبنی بر این که برای هر گراف دو بخشی G کران بالایی برای  X(s) است. که در آن ماکزیمم درجات در میان رئوس دو بخش گراف هستند. نکپرست درستی این حدسی را در حالت نشان م داد. در اینجا این حدس و اثبات نکپرست را بررسی می کنیم. سپس کران بالایی برای اندیس سه نوع حاصل ضرب گراف ها بر حسب اندیس رنگی قوی هر کدادم را از گراف ها و به طور خاص اندیس رنگی قوی تورهای d بعدی برخی تورهای چنبره ای را ابر مکعب های تعمیم یافته را به دست می آوریم. رنگ آمیزی دیگری که در اینجا آن را مد نظر قرار نی دهیم. رنگ آمیزی قوی یالی مجاورتی گراف است. یک رنگ آمیزی قوی یالی مجاورتی گراف g یک رنگ آمیزی یالی سره از گراف g است. به طوری که مجموعه رنگ یال های منتهی به رئوس مجاور گراف مساوی نباشند. کوچکترین عدد (g) را که برای مجموعه رنگ یال های منتهی به رئوس مجاور گراف مساوی نباشند. کوچکترین عدد g  را که با آن تعداد رنگ یک رنگ آمیزی قوی یالی مجاورتی برای گراف g موجود باشد. عدد رنگی قوی یالی مجاورتی گراف نامیده می شود.ژانگ و همکارانش g را این جا به مطالعه این حدس پرداخته و ثابت می کنیم و این حدس برای همه ی گراف های دو بخشی و گراف هایی که در آن ها g=3 برقرار می باشد.

عنوان ها

تعاریف

مقدمه

گراف و زیر گراف ها

گراف های خاص

حاصل ضرب گراف ها

رنگ امیزی گراف ها

فصل دوم: رنگ آمیزی قوی یالی گراف ها

مقدمه

اندیس رنگی قوی هالین گراف معکبی کامل

اندیس رنگی قوی گراف های دو بخشی

اثبات حدس برولدی و کویین در حالت t=2

اندیس رنگی قوی در گراف های دو بخشی sm(k,l) و sm(k,l)

اندیس رنگی قوی حاصل ضرب گراف ها

اندیس رنگی قوی حاصل ضرب کارتزین گراف ها

اندیس رنگی قوی حاصل ضرب کارونگر گراف ها

اندیس رنگی قوی حاصل ضرب قوی گراف ها

فصل سوم: رنگ آمیزی قوی یالی مجاورتی گراف ها

مقدمه

مقدار دقیق اندیس رنگی قوی مجاورتی برخی گراف ها

اندیس رنگی قوی مجاورتی درخت ها

اندیس رنگی

مقدار دقیق اندیس رنگی قوی مجاورتی برخی گراف ها

اندیس رنگی قوی مجاورتی درخت ها

اندیس رنگی قوی مجاورتی دور ها

اندیس رنگی قوی مجاورتی گراف های دو بخشی کامل

اندیس رنگی قوی مجاورتی گراف های کامل

اندیس رنگی قوی مجاورتی گراف k(m,n)

اثبات حدس ژانگ و همکارانش برای گراف g=3 و فاقد یال تنها

اثبات حدس ژانگ و همکارانش برای گراف دو بخشی و فاقد یال تنها

منابع

Abstract

A strong k-edge-coloring of a graph G=(V,E) is a mapping c:E [k] in such a way that any two edges meting at a common vertex, or being adjacent to the san1e edges of G, are assigned different va1ues(colors). The strong chromatic index of G, denoted )(’,(G), is the smallest number k for which G has a strong k-edge-coloring. In this thesis we study the x’5(G), where G is a cubic complete Halin graph, bipartite graph  Sm (k,l) and Sm(k,l). Brualdi and Quinn conjecture that for every bipartite graph G, (’,(G) is bounded byA1A; ,where A1 and A; are the maximum degree among vertices in two partite sets. Nakprasit give the affirmative answer for A1=2. We study this conjecture and give the proof of Nakprasit. Then we present bounds for the chromatic index of three different products of graphs in terms of the strong chromatic index of each factor. In particular, strong chromatic of d-dimensional grids, some of toroidal grids and generalized hypercubes are given. The second graph coloring which we study is adjacent strong edge coloring of graph. An adjacent strong edge coloring of a graph G is a proper edge-coloring of G such that no pair of adjacent vertices meets the same set of colors. The minimum number of colors ;(G) required to give G an adjacent strong edge coloring, is called the adjacent strong edge chromatic number. Zhang and et. Al, give the ;(G) for son1e special graph and conjecture that (G) +2 . Here we study this conjecture and we prove, this conjecture holds for all bipartite graphs and all graphs with (G): 3


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

تعداد صفحات فایل : 122

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

بلا فاصله (اتوماتیک) بعد از پرداخت وجه فایل به ایمیلی که در مرحله بعد وارد می کنید ارسال می شود


خرید فایل پی دی اف یا اسکن شده

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