The Existence Of Special Structures In Edge-colored Graphs

Let G be a simple connected graph.An edge-coloring c of G is an assignment of colors to the edges of G and an edge-weighting w of G is an assignment of weights to the edges of G.A path,a trail,a cycle,or a closed trail of an edge-colored graph G,say F,is called proper in G if every two consecutive edges of F receive different colors.A proper cycle of length three is also referred to as a rainbow triangle.The main results of this thesis are as follows:(1)We present a sufficient condition for the existence of two edge-disjoint triangles in a simple graph,and motivated by this,we provide a sufficient condition for the existence of two edge-disjoint rainbow triangles in an edge-colored graph.Furthermore,a sufficient condition for the existence of two vertex-disjoint triangles in a connected graph is also obtained.(2)For edge-colored weighted graph G=(G,c,w)and two non-adjacent vertices s and t in G,we study the problems for finding,in G,the minimum weighted proper s-t-path,the minimum weighted proper s-t-trail,the minimum weighted proper cycle,the minimum weighted proper closed trail,the maximum weighted proper s-t-path,and the maximum weighted proper s-t-trail.When the minimization problems are considered we assume that G has no negative proper cycle,and when the maximization problems are considered we assume that G has no proper closed trail.We show that all these problems are solvable in polynomial time.