最大度为5的图的Alcuin数

The Alcuin number of graphs with maximum degree five

1000多年前,英国著名学者Alcuin曾提出过一个古老的渡河问题,即狼、羊和卷心菜的渡河问题.最近,Prisner和Csorba等人把这一问题推广到任意的"冲突图"G=(V,E)上,考虑了一类情况更一般的运输计划问题.现在监管者欲运输V中的所有"物品/点"渡河,这里V的两个点邻接当且仅当这两个点为冲突点.冲突点是指不能在无人监管的情况下留在一起的点.特别地,Alcuin渡河问题可转化成"冲突路"P_3上是否存在可行运输方案问题.图G的Alcuin数是指图G具有可行运输方案(即把V的点代表的"物品"全部运到河对岸)时船的最小容量.最大度为5且覆盖数至少为5的图和最大度Δ(G)≤4且覆盖数不小于Δ(G)-1的图的Alcuin数已经被确定.本文给出最大度为4且覆盖数不超过2和最大度为5且覆盖数不超过4的图的Alcuin数.至此,最大度不超过5的图的Alcuin数被完全确定.

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 conflict 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 conflicting 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 conflict 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 Δ（G）- 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.