چکیده

برای رئوس u,v از گراف همبند G با مرتبه n طول بلندترین u-v مسیر در G به وسیله D(u,v) نشان داده می شود رنگ امیزی   هامیلتونی c از گراف G بر چسبگذاری برای رئوس موسوم به رنگ است به طوری که برای هر دو راس متفاوت u,v از گراف G  داشته باشیم:

D(u,v) +|c(u)-c(v)≥n – 1

مقدار hc(C)  رنگ امیزی هامیلتونی c از گراف G بیشترین رنگ اختصاصی داده شده است یک راس از G توسط C است و عدد رنگی هامیلتونی G که ان را با   hc(Cنمایش می دهیم برار است با min{ hc(c)} که مینیمم روی تمامی رنگ امیزی های هامیلتونی G گرفته شده است.سعی ما بر این است که این نوع رنگ امیزی را برای کلاس های مختلف از گراف ها بررسی کنیم در این راه از مقاله های 1.رنگ امیزی هامیلتونی گراف تالیف گری چاترند لادیسلاونبسکی و پینگ ژانگ

2.رنگ امیزی هامیلتونی برای برخی از گراف ها تالیف یوفا شن وجین هی زائو لیو دانگونگ هی و ژیاجینگ یانگ استفاده گردید.

کلمات کلیدی :رنگ امیزی هامیلتونی رنگ امیزی رادیویی و رنگ امیزی متقابل.

فهرست مطالب

1.تعاریف و مفاهیم اولیه

تعاریف و مفاهیم اولیه 2

2.تاریخچه و قضیه های مهم در رنگ امیزی هامیلتونی گراف ها

1.2. تاریخچه رنگ امیزی هامیلتونی گراف ها 10

2.2.1. رنگ امیزی هامیلتونی  برخی گراف ها 11

2.2.2. رنگ امیزی هامیلتونی گراف هایی که با  افزودن 1 یا 2 یال اویزان به گرافی هامیلتونی به دست امده اند 13

2.2.3. رنگ امیزی گراف ها چند بخشی 16

2.2.4. عدد رنگی  هامیلتونی دورها 20

2.2.5.خانواده ای از گراف ها با عدد رنگی هامیلتونی 2 25

2.2.6.ساختن گراف هایی با عدد رنگی هامیلتونی دلخواه 27

3.2.رنگ امیزی هامیلتونی و محیط گراف 29

4.2.محیط و دنباله رنگ های رنگ امیزی هامیلتونی یک گراف 33

3.رنگ امیزی هامیلتونی درخت ها

1.3.قضیه های مهم در رنگ امیزی درخت ها 39

2.3.رنگ ایزی هامیلتونی هزارپا 45

3.3.رنگ امیزی هامیلتونی دو ستاره 49

فهرست شکلها

شکل 1.1. 5

1.2.رنگ امیزی هامیلتونی C0 از G 2.2.رنگ امیزی متقابل C از G 12

3.2.رنگ امیزی C1از Hn 14

4.2.رنگ امیزی هامیلتونی c5,c4,c3 21

5.2.رنگ امیزی هاملیتونی Cn برای د≥6  n 22

6.2.رنگ امیزی p1 23

7.2.گراف هایی از مرتبه  ≤ 5 n ≥ 3 که عدد رنگی هامیلتونی ان ها 2 است 25

8.2.گراف هایی با اعداد رنگی هامیلتونی 2  26

9.2.رنگ امیزی c از G 28

1.3.m=2k+1,  C(m.d) 45

2.3. C(m.d)  با  m=2k 47

3.3.دوستاره k2(n1,n2) 49

 


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

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

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