18314

۱۸۳۱۴

m-رنگ آميزي تام برخي از گراف هاي جانسون و كنسر

كارشناسي ارشد

رياض محض - جبر

آبان ماه ۱۳۹۶

دكتر مهدي علائيان

دكتر زهره مستقيم

رياضي

چكيده m-رنگ آميزي تام با ماتريس A = {aij}i,j=1,••• ,mبراي گراف (G(V, E يك رنگ آميزي راس هاي V با رنگ هاي {1, • • • , m}است به نحوي كه تعداد راس هاي به رنگ j مجاور با يك راس ثابت به رنگ i برابر aijاست،ومستقل از انتخاب رنگ هاي i,j مي باشد.ماتريس A،ماتريس پارامترm-رنگ آميزي تام ناميده مي شود.افراز متناظر مجموعه راس ها را افراز منصفانه ناميده مي شود. در حقيقت،هر رده از افرازمنصفانه شامل راس هاي با رنگ يكسان است. اين پايان نامه همه ماتريس هاي پارامتر2 - رنگ آميزي تام گراف جانسون (J(10,3و همه ماتريس هاي پارامتر 3- رنگ آميزي تام گراف هاي جانسون (J(4,2), J(5,2), J(6,2), J(6,3 و گراف پترسن و2 - رنگ آميزي تام گراف هاي كنسر (K(5,2), K(6,2), K(7,2), K(7,3 را به دست مي آورد.

1396/10/19

1/9/2018 12:00:00 AM

Abstract Under a perfect m-coloring with matrix A = {aij}i,j=1,••• ,m of graph G(V, E) we understand a coloring of the vertices V with the colors {1, • • • , m} such that the number of vertices of color j adjacent to a fixed vertex of color i is equal to aij independently of the choice of colors j and i. The matrix A is called the parameter matrix of a perfect coloring. The corresponding partition of the vertex set is known as equitable. In fact, each class of the equitable partition contains the vertices with same color. This thesis exhausts all parameter matrices of perfect 2-coloring of the Johnson graph J(10,3) and all parameter matrices of perfect 3- coloring of the Johnson graphs J(4,2), J(5,2), J(6,2), J(6,3) and Petersen graph and parameter matrices of perfect 2-coloring of the Kneser graphs K(5,2), K(6,2), K(7,2), K(7,3).