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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Csorba, P., Hurkens, C. A. J. and Woeginger, G. J., The Alcuin number of a graph and its connections to the vertex cover number, SIAM Review, 54(1), 2012, 141–154.
Csorba, P., Hurkens, C. A. J. and Woeginger, G. J., The Alcuin number of a graph, Lecture Notes in Comput. Sci., 5193, Springer-Verlag, Berlin, 2008, 320–331.
Prisner, E., Generalizing the wolf-goat-cabbage problem, Electron. Notes Discrete Math., 27, 2006, 83.
Lampis, M. and Mitsou, V., The ferry cover problem, Theory Comput. Syst., 44, 2009, 215–229.
Shan, E. F., Kong, L. and Kang, L. Y., The Alcuin number of graphs with maximum degree five, Sci. Sin. Math., 44, 2014, 719–728 (in Chinese).
Shan, E. F. and Kong, L., The Alcuin number of a hypergraph and its connections to the transversal number, Operations Research Transactions, 18(3), 2014, 104–110 (in Chinese).
Seify, A. and Shahmohamad, H., Some new results in the Alcuin number of graphs, Bull. Inst. Combin. Appl., 74, 2015, 37–46.
Turán, P., An extremal problem in graph theory (hungarian), Mat. Fiz. Lapok, 48, 1941, 436–452.
Zhu, K. L. and Shan, E. F., River crossing problem on graphs with cover number at most three, Operations Research and Manegement Science, 27(8), 2018, 79–83 (in Chinese).
Gong, C. and Lin, Y., Equivalent properties for CD inequalities on graphs with unbounded Laplacians, Chinese Annals of Mathematics Ser. B, 38(5), 2017, 1059–1070.
Krzywkowski, M., On the ratio between 2-domination and total outer-independent domination numbers of trees, Chinese Annals of Mathematics Ser. B, 34(5), 2013, 765–776.
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was supported by the National Natural Science Foundation of China (Nos. 11871329, 11571222).
Rights and permissions
About this article
Cite this article
Shan, E., Kang, L. The Ferry Cover Problem on Regular Graphs and Small-Degree Graphs. Chin. Ann. Math. Ser. B 39, 933–946 (2018). https://doi.org/10.1007/s11401-018-0105-5
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11401-018-0105-5