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

Path Saturation Game on Six Vertices

  • Paul Balister,
  • Ali Dogan

摘要

Given a family \(\mathcal {F}\) F of graphs, we say that a graph G is \(\mathcal {F}\) F -saturated if G does not contain any member of  \(\mathcal {F}\) F , but for any edge \(e\in E(\overline{G})\) e E ( G ¯ ) the graph \(G+e\) G + e does contain a member of  \(\mathcal {F}\) F . The \(\mathcal {F}\) F -saturation game is played by two players starting with an empty graph and adding an edge on their turn without making a member of \(\mathcal {F}\) F . The game ends when the graph is \(\mathcal {F}\) F -saturated. One of the players wants to maximize the number edges in the final graph, while the other wants to minimize it. The game saturation number is the number of edges in the final graph given the optimal play by both players. In the present paper we study \(\mathcal {F}\) F -saturation game when \(\mathcal {F}=\{P_6\}\) F = { P 6 } consists of the single path on 6 vertices.