Paths and trails in edge-colored weighted graphs

摘要

Let (G, c, w) be an edge-colored weighted graph, where G is a nontrivial connected graph, c is an edge-coloring of G, and w is an edge-weighting of G. A path, a trail, a cycle, or a closed trail of G, say F, is called proper under the edge-coloring c if every two consecutive edges of F receive different colors in c. Let s and t be two specified nonadjacent vertices in G. In this paper, we study the problems for finding, in (G, c, w), 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, c, w) has no negative proper cycle, and when the maximization problems are considered we assume that (G, c, w) has no proper closed trail. We show that all these problems are solvable in polynomial time. (C) 2019 Elsevier B.V. All rights reserved.