|
|
| |
| The Ferry Cover Problem on Regular Graphs and Small-Degree Graphs |
| |
Citation： |
Erfang SHAN,Liying KANG.The Ferry Cover Problem on Regular Graphs and Small-Degree Graphs[J].Chinese Annals of Mathematics B,2018,39(6):933~946 |
| Page view： 733
Net amount： 715 |
Authors： |
Erfang SHAN; Liying KANG |
Foundation： |
This work was supported by the National Natural Science
Foundation of China (Nos.11871329, 11571222). |
|
|
| 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 |
Classification： |
05C70, 90B06 |
|
|
Download PDF Full-Text
|
|
|
|
