<p>In 1982, Harary introduced the concept of Ramsey achievement game on graphs. Given a graph <i>F</i> with no isolated vertices, consider the following game played on the complete graph <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(K_n\)</EquationSource> </InlineEquation> by two players Alice and Bob. First, Alice colors one of the edges of <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(K_n\)</EquationSource> </InlineEquation> blue, then Bob colors a different edge red, and so on. The first player who can complete the formation of <i>F</i> in his color is the winner. The minimum <i>n</i> for which Alice has a winning strategy is the achievement number of <i>F</i>, denoted by <i>a</i>(<i>F</i>). If we replace <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(K_n\)</EquationSource> </InlineEquation> in the game by the complete bipartite graph <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(K_{n,n}\)</EquationSource> </InlineEquation>, we get the bipartite achievement number, denoted by <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(\operatorname {ba}(F)\)</EquationSource> </InlineEquation>. In this paper, we correct <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(\operatorname {ba}(mK_2)=m+1\)</EquationSource> </InlineEquation> to <i>m</i> and disprove <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(\operatorname {ba}(K_{1,m})=2m-2\)</EquationSource> </InlineEquation> from Erickson and Harary (1983). We also find the exact values or upper and lower bounds of bipartite achievement numbers on matchings, stars, and double stars.</p>

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

Ramsey achievement games on graphs : algorithms and bounds

  • Xiumin Wang,
  • Zhong Huang,
  • Xiangqian Zhou,
  • Ralf Klasing,
  • Yaping Mao

摘要

In 1982, Harary introduced the concept of Ramsey achievement game on graphs. Given a graph F with no isolated vertices, consider the following game played on the complete graph \(K_n\) by two players Alice and Bob. First, Alice colors one of the edges of \(K_n\) blue, then Bob colors a different edge red, and so on. The first player who can complete the formation of F in his color is the winner. The minimum n for which Alice has a winning strategy is the achievement number of F, denoted by a(F). If we replace \(K_n\) in the game by the complete bipartite graph \(K_{n,n}\) , we get the bipartite achievement number, denoted by \(\operatorname {ba}(F)\) . In this paper, we correct \(\operatorname {ba}(mK_2)=m+1\) to m and disprove \(\operatorname {ba}(K_{1,m})=2m-2\) from Erickson and Harary (1983). We also find the exact values or upper and lower bounds of bipartite achievement numbers on matchings, stars, and double stars.