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

Erfang Shan; Liying Kang

doi:10.1007/s11401-018-0105-5

Chinese Annals of Mathematics, Series B ›› 2018, Vol. 39 ›› Issue (6) : 933 -946. DOI: 10.1007/s11401-018-0105-5

Article

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

Erfang Shan ¹^,²^,^a
, Liying Kang ²

Author information +

History +

PDF

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

Cite this article

Download citation ▾

Erfang Shan, Liying Kang. The Ferry Cover Problem on Regular Graphs and Small-Degree Graphs. Chinese Annals of Mathematics, Series B, 2018, 39(6): 933-946 DOI:10.1007/s11401-018-0105-5

登录浏览全文

4963

注册一个新账户忘记密码

References

Publishing order | Descend order by publishing year | Descend order by cited within

[1]	Csorba P., Hurkens C. A. J., Woeginger G. J.. The Alcuin number of a graph and its connections to the vertex cover number. SIAM Review, 2012, 54(1): 141-154

[2]	Csorba P., Hurkens C. A. J., Woeginger G. J.. The Alcuin number of a graph. Lecture Notes in Comput. Sci., 2008, 5193: 320-331

[3]	Prisner E.. Generalizing the wolf-goat-cabbage problem. Electron. Notes Discrete Math., 2006, 27: 83

[4]	Lampis M., Mitsou V.. The ferry cover problem. Theory Comput. Syst., 2009, 44: 215-229

[5]	Shan E. F., Kong L., Kang L. Y.. The Alcuin number of graphs with maximum degree five. Sci. Sin. Math., 2014, 44: 719-728

[6]	Shan E. F., Kong L.. The Alcuin number of a hypergraph and its connections to the transversal number. Operations Research Transactions, 2014, 18(3): 104-110

[7]	Seify A., Shahmohamad H.. Some new results in the Alcuin number of graphs. Bull. Inst. Combin. Appl., 2015, 74: 37-46

[8]	Turán P.. An extremal problem in graph theory (hungarian). Mat. Fiz. Lapok, 1941, 48: 436-452

[9]	Zhu K. L., Shan E. F.. River crossing problem on graphs with cover number at most three. Operations Research and Manegement Science, 2018, 27(8): 79-83

[10]	Gong C., Lin Y.. Equivalent properties for CD inequalities on graphs with unbounded Laplacians. Chinese Annals of Mathematics Ser. B, 2017, 38(5): 1059-1070

[11]	Krzywkowski M.. On the ratio between 2-domination and total outer-independent domination numbers of trees. Chinese Annals of Mathematics Ser. B, 2013, 34(5): 765-776