关键词: 图论, 渡河问题, 覆盖数, Alcuin数, 独立集

Abstract: More than 1000 years ago, Alcuin of York proposed a classical puzzle involving a wolf, a goat and a bunch of cabbages that needed to be ferried across a river using a boat that only had enough room for one of them. In 2006, Prisner considered a transportation planning problem that generalizes Alcuin’s river crossing problem to scenarios with arbitrary conflict graphs. In a conflict graph G=(V,E), two vertices (items) of V are connected by an edge in E if and only if they are conflicting, and thus they cannot be left together without human supervision. A feasible schedule on a graphG=(V,E) is a plan that all items of V can be ferried across a river unhurt. The Alcuin number of G is the smallest possible capacity of a boat for which the graph G possesses a feasible schedule. In this paper we investigate the Alcuin number of connected graphs with cover number at most three and give a complete characterization on the Alcuin number for the graphs.

Key words: graph theory, river crossing, cover number, Alcuin number, independent set