The Edge-Recoloring Cost of Paths and Cycles in Edge-Colored Graphs and Digraphs

摘要

In this paper we introduce a number of problems regarding edge-color modifications in edge-colored graphs and digraphs. Consider a property π, a c-edge-colored graph G~c (resp., digraph D~c) not satisfying π, and an edge-recoloring cost matrix R = [r_(ij)]_(c×c) where r_(ij) ≥ 0 denotes the cost of changing color i of edge e to color j. Basically, in this kind of problem the idea is to change the colors of one or more edges of G~c (resp., oriented edges in D~c) in order to construct a new c'-edge-colored G_(new)~(c') with c' ≤ c (resp., D_(new)~(c')) such that the total edge-recoloring cost is minimized and property π is satisfied. Here, we are especially concerned with properly edge-colored and monochromatic paths, trails and cycles in graphs and digraphs.