Skip to main content
SUPERVISOR
Behnaz Omoomi,Gholamreza Omidi
بهناز عمومی (استاد راهنما) غلامرضا امیدی اردلی (استاد مشاور)
 
STUDENT
Akbar Davoodi Zavareh
اکبر داودی زواره

FACULTY - DEPARTMENT

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

TITLE

Vertex-Coloring Edge-Weighting of Graphs
A k-total-weighting of a simple graph G is a function w:E(G) ?V (G) ? {1,...,k} . A total-weighting is a vertex-coloring , if for every edge uv ? E(G), c(u) ?c(v), where for every vertex v ? V (G), . If such a function w exists , then we say that G admits a vertex-coloring k-total-weighting (VCk-TW) . The smallest k for which G admits a VCk-TW is denoted by ?(G) . This concept was introduced by Przybylo et al . (DMTCS, Vol . 12, No. 1, pp. 101--108, 2010) , they proposed the conjecture that for every simple graph G , ?(G) ? 2 . This conjecture is known as 1-2-conjecture . So far , the existence of a VC2-TW has been shown for complete graphs , 3-colorable graphs , 3-regular graphs, 4-regular graphs and graphs of maximum degree ? ? 3 . It has been recently shown by Kalkowski et al . (J. Combin. Theory Ser. B, Vol. 100, No. 3, pp. 347--349, 2010) that every graph has a VC3-TW . A k-edge-weighting of a graph G is a function w : E(G) ? {1,...,k} . An edge-weighting naturally induces a vertex coloring c , where for every vertex v ? V (G), . If the induced coloring c is a proper vertex coloring , then w is called a vertex-coloring k-edge-weighting (VCk-EW) . The minimum k for which G admits a VC k-EW is denoted by µ(G). Karo?ski et al . (J . Combin . Theory Ser . B , Vol. 91, pp. 151--157, 2004) introduced this concept and conjectured that every graph admits a VC3-EW . This conjecture is known as 1-2-3-conjecture . Note that if a graph admits a vertex-coloring k-edge-weighting , then it also admits a vertex-coloring k-total-weighting. Hence, µ(G) ? 2 implies trueness of the 1- 2-conjecture. This thesis deals with studying the concept of vertex-coloring edge-weighting of graphs and especially 1 -2-3-conjecture . In Chapter 2 , we review several similar graph parameters which are based on edge-weightings and are interesting in their own right but they also have potential consequences for the chromatic number. In Chapter 3, we investigate the concept of vertex-coloring edge-weighting of graphs. Also we give the proof that for every connected graph G? K2, µ(G) ? 5, which is the best known upper bound for the parameter µ in general case. Then we calculate exact value of µ for some well-known families of graphs like paths, cycles, complete graphs. Finally, we discuss parameter for the cartesian product of graphs. In Chapter 4 we show that 1- 2- 3-conjecture is true for 3-colorable graphs. After that, since if µ(G) ? 2, then 1 - 2-conjecture is also holds for G, we focus on graphs for which the parameter µ can not exceed two. In this way, we give some sufficient conditions for a graph to admit a VC2-EW. We end this chapter by the problem of characterization of bipartite graphs into the two types according to the value of µ . In Chapter 5, we release weights to real numbers and consider the problem of VC 2-EW with two real weights. The new results obtained in this dissertation is prepared in [Davoodi, A. and Omoomi, B., On the 1-2-3-conjecture , submitted].
فرض کنید G یک گراف متناهی، غیرجهت‌دار و ساده با مجموعه رئوس V(G) و مجموعه یال‌های E(G) باشد . یک k -وزن‌دهی یالی مانند w از گراف G یک تخصیص از وزن‌های صحیح w(e)?{ 1, 2, … ,k} به تمام یال‌های G است. به طور طبیعی هر وزن‌دهی یالی w یک رنگ‌آمیزی رأسی از G مانند c القا می‌کند که برای هر رأس v به صورت تعریف می‌شود. اگر برای یک k -وزن‌دهی یالی از گراف G مانند w رنگ‌آمیزی رأسی القایی c مجاز باشد، یعنی برای هر دو رأس مجاور u و v ، c(u) ? c(v) . به چنین رنگ‌آمیزی یک رنگ‌آمیزی رأسی از k-وزن‌دهی یالی گفته ‌می‌شود. کوچک ‌ترین مقدار k که G یک رنگ‌آمیزی رأسی از k-وزن‌دهی یالی دارد با نماد (G)µ نمایش داده می‌شود. در سال 2004 حدس زده شد که برای هر گراف ساده همبند G با حداقل سه رأس ، (G) ? 3µ . مطالعه این حدس که به حدس 1-2-3 شهرت یافته و تاکنون باز است ، محور اصلی این پایان‌نامه را تشکیل می‌دهد. در این پایان‌نامه ضمن جمع‌آوری کلیه نتایجی که در این زمینه به دست آمده ، درستی این حدس برای دسته‌های نامتناهی از گراف‌ها ثابت شده است.

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