Let G=(V,E) be a connected undirected graph with positive edge lengths. Let V={0}ℝN, where N={1,...,n}. Each node in N is identified as a customer, and 0 is the home location of a traveling salesman or repairman who serves the customers in N. Each subset of customers S can hire the repairman to serve its members only. In that case the cost incurred by S, c(S), is the minimum length of a tour traversed by the repairman who starts at node 0, visits each node in S at least once and returns to 0. The paper considers the core of the cooperative cost allocation game (N;c) defined by the cost function c(S), Sℝlsim;N. It shows that the core can be empty even if G is series parallel by presenting the unique minimal counter example for such graphs. The paper then uses a recent result of Fonlupt and Naddef, and proves that the core is nonempty for a class of graphs that properly contains the subclass of cycle trees, i.e. graphs which have no edge included in more than one simple cycle.
