The Ferry Cover Problem on Regular Graphs and Small-Degree Graphs  

The Ferry Cover Problem on Regular Graphs and Small-Degree GraphsThe Ferry Cover Problem on Regular Graphs and Small-Degree Graphs

作　　者：Erfang SHAN Liying KANG 

机构地区：[1]School of Management, Shanghai University, Shanghai 200444, China [2]Department of Mathematics,Shanghai University, Shanghai 200444, China

出　　处：《Chinese Annals of Mathematics,Series B》2018年第6期933-946,共14页数学年刊（B辑英文版）

基　　金：supported by the National Natural Science Foundation of China(Nos.11871329,11571222)

摘　　要：The ferry problem may be viewed as generalizations of the classical wolf-goatcabbage puzzle. The ferry cover problem is to determine the minimum required boat capacity to safely transport n items represented by a conflict graph. The Alcuin number of a conflict graph is the smallest capacity of a boat for which the graph possesses a feasible ferry schedule. In this paper the authors determine the Alcuin number of regular graphs and graphs with maximum degree at most five.

关 键 词：Graph Alcuin number Ferry problem Vertex cover Regular graph 

分 类 号：O157.5[理学—数学]