The Ferry Cover Problem on Regular Graphs and Small-Degree Graphs |
| |
Authors: | Erfang SHAN and Liying KANG |
| |
Institution: | 1.School of Management,Shanghai University,Shanghai,China;2.Department of Mathematics,Shanghai University,Shanghai,China |
| |
Abstract: | The ferry problem may be viewed as generalizations of the classical wolf-goat-cabbage 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. |
| |
Keywords: | Graph Alcuin number Ferry problem Vertex cover Regular graph |
本文献已被 SpringerLink 等数据库收录! |
| 点击此处可从《数学年刊B辑(英文版)》浏览原始摘要信息 |
| 点击此处可从《数学年刊B辑(英文版)》下载免费的PDF全文 |