The Alcuin number of graphs with maximum degree five
Lu KONG, Liying Kang, Erfang Shan · Scientia Sinica Mathematica · 2014
More than 1000 years ago, Alcuin, a famous scholar, proposed a classical puzzle involving a wolf, a goat and a bunch of cabbages. Recently, Prisner and Csorba considered this transportation planning problem that generalizes Alcuin's river crossing problem to arbitrary con ict graphs G = (V,E). Now the man has to transport a set V of items/vertices across the river. Two items are connected by an edge in E if they are con icting and thus cannot be left together without human supervision. In particular, Alcuin's river crossing problem corresponds to the path P3 with three vertices in above graph-theoretic model. The Alcuin number of a con ict graph is the smallest capacity of a boat for which the graph possesses a feasible schedule. The Alcuin number of a graph with maximum degree Δ(G)≤4 and cover number at least Δ(V)-1 or maximum degree 5 and cover number at least 5 has been determined. In this paper we give the Alcuin number of a graph with maximum degree 4 and cover number at most 2 or maximum degree 5 and cover number at most 4.