28698

رنگ آميزي تام روي گراف هاي منظم

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

رياضي- جبر

1399

1402/4/12

مهدي علائيان

دانشكده رياضي

فرض كنيمG=(V,E)گراف ساده با مجموعه رئوسV=V(G) و مجموعه يال هاي E=E(G) باشد.يك m-رنگ آميزي تام با ماتريس M=[m i,j] i,j=1 ,...,m براي G عبارت است از رنگ آميزي راس هاي G با رنگ هاي {1,...m} به نحوي كه تعداد راس هاي به رنگ j مجاور با يه راس ثابت به رنگ i برابر با m i,j و مستقل از انتخاب راس به رنگ i باشد.ماتريس Mماتريس پارامتر رنگ آميزي تام ناميده مي شود. در اين پايان نامه،ماتريس هاي پارامتر تمام 3-رنگ آميزي هاي تام گراف مكعبي Q3 را برمي شماريم.همچنين برخي از نتايج اساسي را براي يك گراف همبند مكعبي از مرتبه 8 ارائه مي كنيم. همچنين حاصلضرب واژگاني(تركيب) گراف مسير نامتناهي و يك گراف G را در نظر مي گيريم كه G مي تواند گراف كامل يا پوچ با n راس باشد.ما شرح كاملي از رنگ آميزي هاي تام با تعداد دلخواه رنگ از اين حاصلضرب واژگاني گراف ارائه ميكنيم.

1402/06/21

Perfect colourings of regular graphs

7/2/2024 12:00:00 AM

Let G=(V,E) be a simple graph with the vertex set V=V(G) and the edge set E=E(G) .A perfect colouring with m colors (a Perfect of m-coloring) with matrix M=[m i,j]i,j=1,...,m of a graph G is a colouring of the vertices of G with the color {1,2,...,m} such that the number of vertices of color j adjacent to a fixed vertex of color i is equal to Mij independently of the choice of the latter vertex. The matrix M is called the parameter matrix of a perfect colouring. We enumerate the parameter matrices of all perfect 3-colourings of the cubical graph Q3.We also present some bisic results for a cubic connected graph of order 8. We consider a lexicographic product of the infinite path graph and a graph G that can bi either the complete or empty graph on n vertices. We give a complete description of perfect colourings with an arbitrary number of colors of such graph products.

رنگ آميزي تام , افراز منصفانه , گراف مكعبي , رنگ هاي هم ارز , گراف چند مسير نامتناهي

Perfect colouring , Equitable partition , Cubical graph , Equivalent colors , Infinite multipath graph

Mohammad Raoof Negahdari

Dr. Mehdi Alaeiyan