On some balanced, totally balanced and submodular delivery games

This paper studies a class of delivery problems associated with the Chinese postman problem and a corresponding class of delivery games. A delivery pr oblem in this class is determined by a connected graph, a cost function def ined on its edges and a special chosen vertex in that graph which will be r eferred to as the post office. It is assumed that the edges in the graph ar e owned by different individuals and thr delivery game is concerned with th e allocation of the traveling costs incurred by the server, who starts at t he post office and is expected to traverse all edges in the graph before re turning to the post office. A graph G is called Chinese postman-submodular, or, for short, CP-submodular (CP-totally balanced, CP-balanced, respective ly) if for each delivery problem in which G is the underlying graph the ass ociated delivery game is submodular (totally balanced, balanced, respective ly). For undirected graphs we prove that CP-submodular graphs and CP-totally bal anced graphs are weakly cyclic graphs and conversely. An undirected graph i s shown to be CP-balanced if and only if it is a weakly Euler graph. For di rected graphs, CP-submodular graphs can be characterized by directed weakly cyclic graphs. Further, it is proven that any strongly connected directed graph is CP-balanced. For mixed graphs it is shown that a graph is CP-submo dular if and only if it is a mixed weakly cyclic graph. Finally, we note that undirected, directed and mixed weakly cyclic graphs c an be recognized in linear time.