Skip to main content
SUPERVISOR
Gholamreza Omidi,Maryam Shahsiah
غلامرضا امیدی اردلی (استاد راهنما) مریم شاه سیاه (استاد مشاور)
 
STUDENT
Ali Arshi
علی عرشی

FACULTY - DEPARTMENT

دانشکده ریاضی
DEGREE
Master of Science (MSc)
YEAR
1392

TITLE

Mono-multi bipartite Ramsey numbers, designs and matrices
Bialostocki and Voxman may have been iired by the definition of H(n) y Erdos and Graham when they defined for a given graph G , the number RM(G) to e the mallest integer N such that if the edges of the complete graph K N are colored with any number of colors , then , for the resulting coloring , there is either a monochromatic or a rainbow copy of G . They howed that this number exists if and only if G is acyclic . Eroh extended this definition when she defined , for two graphs G 1 and G 2 (without isolated vertices) , the rainbow ramsey number RR(G 1 ; G 2 ) to be the least positive integer such that if the edges of K N are colored with any number of colors , the resulting graph contains either a monochromatic copy of G 1 or a rainbow copy of G 2 . RR(G 1 ; G 2 ) exists if and only if G 1 is a tar or G 2 is a forest . Hence the existence of RR(G 1 ; G 2 ) requires that either G 1 or G 2 be ipartite . This observation and the notion of ipartite ramsey numbers suggests an other ramsey concept . Given two bipartite graphs G 1 and G 2 (without isolated vertices) , the bipartite rainbow ramsey number BRR(G 1 ; G 2 ) is the smallest integer N such that any edge-coloring of K N,N contains a monochromatic copy of G 1 or a rainbow copy of G 2 . An edge coloring of a graph G is assigning colors to the edges of G . A graph with colored edges is said to be monochromatic if all its edges have the same color and is aid to be rainbow if no two of its edges have the same color . For the various applications of graph coloring , different extentions of this notion defined and were studied . One of these extentions is the ipartite rainbow ramsey number , that will be studied here . Eroh and Oellerman considered the bipartite rainbow Ramsey numbers for bipartite graphs : It is shown that RR(G 1 ; G 2 ) exists if and only if G 1 is a star or G 2 is a star forest . Among many results they proved is that BRR(K 1, ? ,K r,s ) = O(?) for fixed r , s . In particular , for r = s = 2 they showed that 3? - 2 ? BRR(K 1,? ,K 2,2 ) ? 6?- 8 . Exact values and bounds for BRR(G 1 ; G 2 ) for various pairs of graphs G 1 and G 2 for which the bipartite ramsey number is defined are established . In the thesis we study the bipartite rainbow ramsey number RR(G 1 ; G 2 ) for G 1 =K 1,? and G 2 =K 2,2 . We also study the bounds for bipartite rainbow ramsey number BRR(K 1,? ,K r,s ) for positive integers r and . Another roblem is finding the least integer so that every edge coloring of the complete graph K ? ,n contains a monochromatic copy of K 1,? or a rainbow copy of K 2,2 .
فارسی یک رنگ آمیزی یالی برای گراف دلخواه G اختصاص رنگ به یال‌های گراف است. در صورتی که در رنگ آمیزی یالی G همه یال‌ها رنگ یکسان داشته باشند، گراف را تک رنگ گوییم و در صورتی که هیچ دو یالی دارای رنگ یکسان نباشد، گراف را رنگین‌کمانی گوییم. به دلیل جذابیت‌های کاربردی و تحقیقاتی مفهوم رنگ آمیزی، تا کنون تعمیم‌‌های گوناگونی از رنگ آمیزی یالی تعریف شده و مورد بررسی قرار گرفته است. در این پایان‌نامه مفهوم عدد رمزی دوبخشی رنگین‌کمانی مورد بررسی قرار می‌گیرد که تعمیمی از رنگ آمیزی یالی روی گراف‌های دوبخشی کامل است. دو گراف دوبخشی G 1 و G 2 داده شده است. عدد رمزی دوبخشی رنگین‌کمانی RR(G 1 , G 2 ) برابرکوچکترین عدد N است به طوری که هر رنگ آمیزی یالی از گراف دوبخشی کامل K N,N با هر تعداد دلخواه رنگ، شامل یک کپی تک رنگ از G 1 و یا شامل یک کپی رنگین‌کمانی از G 2 باشد. کران‌ها و مقادیر دقیق بسیاری برای این عدد با در نظر گرفتن G 1 و G 2 های مختلف بدست آمده است. هدف ما در این پایان‌نامه بررسی مقدار دقیق این عدد به ازای گراف‌های دوبخشی G 1 =K 1,? و G 2 =K 2,2 است.

ارتقاء امنیت وب با وف بومی