On the core of a traveling salesman cost allocation game (Q1122517)

A traveling salesman game is considered. The aim is to allocate his trip cost among the customers. Stable allocations belong to the corresponding cooperative game core. The characteristic function for every coalition is given by the solution of the traveling salesman problem for these very customers. The emptiness of the core for hypohamiltonian graphs is proved. Three more graphs with empty core are shown. Sufficient conditions on a graph which ensure the nonemptiness of the core are given. They require that the graph contains no minor which is isomorphic to one of the three above graphs. If the graph satisfies these conditions it is possible to compute a core allocation by solving a linear program of polynomial dimensions.