<p>Given a graph <i>G</i> and a family of graphs <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\mathcal F\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">F</mi> </math></EquationSource> </InlineEquation>, an <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\mathcal F\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">F</mi> </math></EquationSource> </InlineEquation>-isolating set, as introduced by Caro and Hansberg, is any set <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(S\subset V(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>S</mi> <mo>⊂</mo> <mi>V</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> such that <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(G - N[S]\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo>-</mo> <mi>N</mi> <mo stretchy="false">[</mo> <mi>S</mi> <mo stretchy="false">]</mo> </mrow> </math></EquationSource> </InlineEquation> contains no member of <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(\mathcal F\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">F</mi> </math></EquationSource> </InlineEquation> as a subgraph. In this paper, we introduce a game in which two players with opposite goals are together building an <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(\mathcal F\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">F</mi> </math></EquationSource> </InlineEquation>-isolating set in <i>G</i>. Following the domination games, Dominator (Staller) wants that the resulting <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(\mathcal F\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">F</mi> </math></EquationSource> </InlineEquation>-isolating set obtained at the end of the game, is as small (as big) as possible, which leads to the graph invariant called the game <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(\mathcal F\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">F</mi> </math></EquationSource> </InlineEquation>-isolation number, denoted <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(\iota _\textrm{g}(G,\mathcal F)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>ι</mi> <mtext>g</mtext> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo>,</mo> <mi mathvariant="script">F</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>. We prove that the Continuation Principle holds in the <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\(\mathcal F\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">F</mi> </math></EquationSource> </InlineEquation>-isolation game, and that the difference between the game <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\(\mathcal F\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">F</mi> </math></EquationSource> </InlineEquation>-isolation numbers when either Dominator or Staller starts the game is at most 1. Considering two arbitrary families of graphs <InlineEquation ID="IEq12"> <EquationSource Format="TEX">\(\mathcal F\)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">F</mi> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq13"> <EquationSource Format="TEX">\(\mathcal F'\)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi mathvariant="script">F</mi> <mo>′</mo> </msup> </math></EquationSource> </InlineEquation>, we find relations between them that ensure <InlineEquation ID="IEq14"> <EquationSource Format="TEX">\(\iota _\textrm{g}(G,{\mathcal {F}}') \le \iota _\textrm{g}(G,{\mathcal {F}})\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>ι</mi> <mtext>g</mtext> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo>,</mo> <msup> <mrow> <mi mathvariant="script">F</mi> </mrow> <mo>′</mo> </msup> <mo stretchy="false">)</mo> </mrow> <mo>≤</mo> <msub> <mi>ι</mi> <mtext>g</mtext> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo>,</mo> <mi mathvariant="script">F</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> for any graph <i>G</i>. A special focus is given on the isolation game, which takes place when <InlineEquation ID="IEq15"> <EquationSource Format="TEX">\(\mathcal {F}=\{K_2\}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">F</mi> <mo>=</mo> <mo stretchy="false">{</mo> <msub> <mi>K</mi> <mn>2</mn> </msub> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation>. We prove that <InlineEquation ID="IEq16"> <EquationSource Format="TEX">\(\iota _\textrm{g}(G,\{K_2\})\le |V(G)|/2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>ι</mi> <mtext>g</mtext> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo>,</mo> <mrow> <mo stretchy="false">{</mo> <msub> <mi>K</mi> <mn>2</mn> </msub> <mo stretchy="false">}</mo> </mrow> <mo stretchy="false">)</mo> </mrow> <mo>≤</mo> <mrow> <mo stretchy="false">|</mo> <mi>V</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">|</mo> </mrow> <mo stretchy="false">/</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> for any graph <i>G</i>, and conjecture that <InlineEquation ID="IEq17"> <EquationSource Format="TEX">\(\lceil 3|V(G)|/7\rceil \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo>⌈</mo> <mn>3</mn> <mo stretchy="false">|</mo> <mi>V</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo stretchy="false">|</mo> <mo stretchy="false">/</mo> <mn>7</mn> <mo>⌉</mo> </mrow> </math></EquationSource> </InlineEquation> is the actual (sharp) upper bound. We prove that the isolation game on a forest when Dominator has the first move never lasts longer than the one in which Staller starts the game. Finally, we prove good lower and upper bounds on the game isolation numbers of paths <InlineEquation ID="IEq18"> <EquationSource Format="TEX">\(P_n\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>P</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation>, which lead to the exact values <InlineEquation ID="IEq19"> <EquationSource Format="TEX">\(\iota _\textrm{g}(P_n,\{K_2\})=\left\lfloor \frac{2n+2}{5}\right\rfloor \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>ι</mi> <mtext>g</mtext> </msub> <mrow> <mo stretchy="false">(</mo> <msub> <mi>P</mi> <mi>n</mi> </msub> <mo>,</mo> <mrow> <mo stretchy="false">{</mo> <msub> <mi>K</mi> <mn>2</mn> </msub> <mo stretchy="false">}</mo> </mrow> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mfenced close="⌋" open="⌊"> <mfrac> <mrow> <mn>2</mn> <mi>n</mi> <mo>+</mo> <mn>2</mn> </mrow> <mn>5</mn> </mfrac> </mfenced> </mrow> </math></EquationSource> </InlineEquation> when <InlineEquation ID="IEq20"> <EquationSource Format="TEX">\(n \equiv i \pmod 5\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>≡</mo> <mi>i</mi> <mspace width="4.44443pt" /> <mo stretchy="false">(</mo> <mo>mod</mo> <mspace width="0.277778em" /> <mn>5</mn> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq21"> <EquationSource Format="TEX">\(i \in \{1,2,3\}.\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>i</mi> <mo>∈</mo> <mo stretchy="false">{</mo> <mn>1</mn> <mo>,</mo> <mn>2</mn> <mo>,</mo> <mn>3</mn> <mo stretchy="false">}</mo> <mo>.</mo> </mrow> </math></EquationSource> </InlineEquation></p>

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

Isolation Game on Graphs

  • Boštjan Brešar,
  • Tanja Dravec,
  • Daniel P. Johnston,
  • Kirsti Kuenzel,
  • Douglas F. Rall

摘要

Given a graph G and a family of graphs \(\mathcal F\) F , an \(\mathcal F\) F -isolating set, as introduced by Caro and Hansberg, is any set \(S\subset V(G)\) S V ( G ) such that \(G - N[S]\) G - N [ S ] contains no member of \(\mathcal F\) F as a subgraph. In this paper, we introduce a game in which two players with opposite goals are together building an \(\mathcal F\) F -isolating set in G. Following the domination games, Dominator (Staller) wants that the resulting \(\mathcal F\) F -isolating set obtained at the end of the game, is as small (as big) as possible, which leads to the graph invariant called the game \(\mathcal F\) F -isolation number, denoted \(\iota _\textrm{g}(G,\mathcal F)\) ι g ( G , F ) . We prove that the Continuation Principle holds in the \(\mathcal F\) F -isolation game, and that the difference between the game \(\mathcal F\) F -isolation numbers when either Dominator or Staller starts the game is at most 1. Considering two arbitrary families of graphs \(\mathcal F\) F and \(\mathcal F'\) F , we find relations between them that ensure \(\iota _\textrm{g}(G,{\mathcal {F}}') \le \iota _\textrm{g}(G,{\mathcal {F}})\) ι g ( G , F ) ι g ( G , F ) for any graph G. A special focus is given on the isolation game, which takes place when \(\mathcal {F}=\{K_2\}\) F = { K 2 } . We prove that \(\iota _\textrm{g}(G,\{K_2\})\le |V(G)|/2\) ι g ( G , { K 2 } ) | V ( G ) | / 2 for any graph G, and conjecture that \(\lceil 3|V(G)|/7\rceil \) 3 | V ( G ) | / 7 is the actual (sharp) upper bound. We prove that the isolation game on a forest when Dominator has the first move never lasts longer than the one in which Staller starts the game. Finally, we prove good lower and upper bounds on the game isolation numbers of paths \(P_n\) P n , which lead to the exact values \(\iota _\textrm{g}(P_n,\{K_2\})=\left\lfloor \frac{2n+2}{5}\right\rfloor \) ι g ( P n , { K 2 } ) = 2 n + 2 5 when \(n \equiv i \pmod 5\) n i ( mod 5 ) and \(i \in \{1,2,3\}.\) i { 1 , 2 , 3 } .