The first paper of convexity on general graphs, in English, is the paper “Convexity in graphs”, published in 1981. One of its authors, Frank Harary, introduced in 1984 the first graph convexity games, focused on the geodesic convexity, which are impartial games and were investigated in a sequence of five papers until 2003. Only in 2023 the first PSPACE-hardness result on impartial convexity games were proved. In this paper, we introduce the partizan variants of these impartial games on the geodesic convexity and extend them to other graph convexities, obtaining winning strategies and complexity results. Among them, we obtain winning strategies for general convex geometries and winning strategies for trees from Conway’s combinatorial game theory on partizan games. We also prove that the normal play and the misère play of the partizan hull game on the geodesic convexitiy is PSPACE-complete even in graphs with diameter two.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Graph Convexity Partizan Games: Complexity and Winning Strategies

  • Samuel N. Araújo,
  • J Marcos Brito,
  • Raquel Folz,
  • Rosiane de Freitas,
  • Rudini Sampaio

摘要

The first paper of convexity on general graphs, in English, is the paper “Convexity in graphs”, published in 1981. One of its authors, Frank Harary, introduced in 1984 the first graph convexity games, focused on the geodesic convexity, which are impartial games and were investigated in a sequence of five papers until 2003. Only in 2023 the first PSPACE-hardness result on impartial convexity games were proved. In this paper, we introduce the partizan variants of these impartial games on the geodesic convexity and extend them to other graph convexities, obtaining winning strategies and complexity results. Among them, we obtain winning strategies for general convex geometries and winning strategies for trees from Conway’s combinatorial game theory on partizan games. We also prove that the normal play and the misère play of the partizan hull game on the geodesic convexitiy is PSPACE-complete even in graphs with diameter two.