可在www.sciencedirect.com在线获取理论计算机科学电子笔记346（2019）473-484www.elsevier.com/locate/entcs庄家-庄家支配游戏的快速获胜策略瓦伦丁·格莱代尔百合花Universit'eLyon 1Lyon，FranceVesnaIrsic卢布尔雅那大学数学和物理学院斯洛文尼亚卢布尔雅那Sandi KlavZarzar卢布尔雅那大学数学和物理学院斯洛文尼亚卢布尔雅那摘要制造者-破坏者控制博弈是由Dominator和Staller在图G上进行的。玩家可以选择在游戏过程中还没有选择的G的顶点。支配者赢，如果在某些点上，他所选择的顶点形成了一个支配集。如果支配者不能形成，则Staller获胜一个支配集本文引入了G的Maker-Breaker控制数γMB（G），它是当Dominator有获胜策略且首先使用时，他赢得博弈的最小步数.若Staller平面是第一个，则相应的i_v_n_t记为γM′B（G）. 比较这两个不变量，结果表明它们的行为与相关的博弈控制数有很大的不同。并将非变量γMB（G）与控制数进行了比较. 利用ErdBronos-Selfridge准则，找到了一类满足γMB（G）>γ（G）的图G.引入了残差图，并用它来确定γMB（G）和γM′B（G）. 利用剩余图，确定了任意树的γMB（T）和γM′B（T）.还得到了循环的不变量。 一个开放的问题和进一步调查的方向清单。关键词：Maker-Breaker控制对策，Maker-Breaker控制数，控制对策，完美匹配，树，圈制造者-破坏者博弈（以及其他位置博弈）由ErdBaglios和Selfridge在[13]中引入，从那时起就成为了大量研究的主题，参见[2，3，14，15]。Maker-Breaker游戏是由两个名为Maker和Breaker的玩家在超图上玩的。他们轮流，在每一轮当前的球员选择一个新的顶点。庄家赢，如果在游戏的某个点，他选择了https://doi.org/10.1016/j.entcs.2019.08.0421571-0661/© 2019作者。出版社：Elsevier B.V.这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。474诉Gledel等人/理论计算机科学电子笔记346（2019）473所有顶点从其中一个超边，而断路器赢了，如果她能阻止他这样做[1]和[16]是关于这个领域的一般介绍最近，制造者-破坏者统治游戏在[12]中引入。这个游戏是在一个图G上进行的，有两个名为Dominator和Staller的玩家。选择这些名称是为了强调游戏的统治性质，并与通常的统治游戏保持一致，其中这两个名称现在是标准的。(The支配博弈在[4]中被引入，并在几十篇论文中得到了进一步的研究，参见。[6、11、22、23、24]。玩家可以选择在游戏过程中还没有选择的G的顶点。 如果在某一点上，支配者选择的顶点形成支配集，则支配者获胜。如果支配者不能形成支配集，则拖延者获胜。 请注意，制造者-破坏者统治游戏是一个制造者-决胜局。事实上，如果对于一个图G，我们建立一个超图F，的顶点为G，且其中超边为G的控制集，则Dominator赢得G上的Maker-Breaker控制博弈当且仅当Maker赢得F上的Maker-Breaker博弈.在几篇关于庄家-断路器游戏的论文中，作者对庄家获胜所需的最小移动数感兴趣，见[7，8，15]。此外，在[12]中强调，在处理庄家-庄家博弈时，有两个自然的问题：（i）哪个玩家有获胜策略;（ii）如果统治者有获胜策略，最少走多少步。在开创性的论文中，问题（i）进行了研究，而在本文中，我们研究（ii）。为此，我们说，如果G是一个图，则G的Maker-Breaker控制数γMB（G）G是支配者赢得游戏的最小移动次数，前提是他有一个获胜的策略，他是第一个上场的。否则设γMB（G）= ∞。类似地，γMJB（G）表示Staller首先参与的博弈中支配者的最小移动次数.我们按以下步骤进行。在下一节中，我们列出了本文所需的额外定义和几个已知结果，以及证明了Maker-Breaker控制数的一些基本结果。 在第2节中，我们首先比较γMB（G）与γMJB（G）的相关对策域，并发现它们与相关对策域完全不同。国家不变量我们还比较了γMB（G）与控制数的关系，并利用Eld-Selfridge准则证明了如果G的γ-集的个数不等于0，大，则γMB（G）> γ（G）。在第3节中，我们介绍剩余图，确定（分别）。bound）γMJB（G）（resp. γMB（G）），并确定了任意树的γMB（T）和γMJB（T）.在下一节中，我们得到了循环的变量。 最后，我们列出了一系列悬而未决的问题和进一步发展的调查事务所1预赛设G=（V，E）是一个图. 图G中与叶相邻的顶点是图G的支撑点。 G的完美匹配是覆盖V（G）的两两独立边的集合。G的阶用n（G）表示。如果u是G的一个顶点，则N[u]表示u的闭邻域。如果v是另一个顶点，则我们设置N[u，v] =N[u]<$N[v]。诉Gledel等人/理论计算机科学电子笔记346（2019）473475一个集合D<$V（G）是G的一个控制集，如果<$u∈DN[u] =V（G）.控制数γ（G）是G的最小控制集的大小。一个大小为γ（G）的控制集称为G的γ-集。制造者-破坏者支配博弈被称为D-博弈。S-game）if Domi- nator（resp.第一个是玩游戏。在D-对策中选择的顶点序列将用d1，s1，d2，s2，.表示。. 和SJ1，DJ1，SJ2，DJ2， . . 假设支配者赢了一场 D-游戏。然后最后一个顶点是支配者，让它是dk。游戏的定义{d1，.，dk}是G的一个控制集. 类似地，如果支配者赢得S-游戏并且由支配者给出的最后一个顶点是dJ1，则n{dJ1， . ，dJl}是G.如果Staller的一步棋为她在下一步棋中获胜创造了两种可能性，并且因此支配者不能阻止Staller获胜，那么我们说Staller的一步棋是双重威胁。设G是一个图，k ≥ 1，u1，…， u k，v1，.，的v k两两 相异顶点G. 然后我们说X ={{u1，v1}，. {uk，vk}}是一个配对支配集，如果KN[u i，v i] = V（G）.i=1如果X ={{u1，v1}，...，{uk，vk}}是一个配对控制集，使得uivi∈E（G）对i∈[k]成立，则称X是一个控制匹配.在下文中，我们将通过[12，命题9]中证明的以下解释来使用这个概念引理1.1设u1，...，u k，v1，.，vk是图G的两两相异顶点，设X ={{u1，v1}，.，{u k，v k}}。 则X是一个配对控制集，如果且只有当每个集合{x1，...，xk}，其中xi ∈{ui，vi}，i∈ [k]，是G的一个控制集.这个引理的一个直接应用是下面的事实。事实1.2[12，命题10]如果G允许一个配对支配集，那么在D-博弈和S-博弈中，支配者在G上都有一个获胜策略。事实1.2的逆命题一般不成立。例如，在[12，图4]中，给出了一个弦图，在该弦图上，支配者在两个博弈中都有获胜策略，但不承认配对支配集。另一方面，在树类中相反，因为如果Dominator在树T上有一个获胜策略，那么在[12]中证明了T有一个支配匹配。此外，逆也适用于余图。引理1.3（无跳引理）在支配者实现γM B（G）或γMJB（G）的最优策略中，跳过一步对他来说永远不是优势。更重要的是，如果Staller跳过一步，它只能是统治者的优势。设G是一个图，S∈V（G），则设G|S表示图G，其中来自S的顶点被声明为已经被支配，也就是说，支配者没有义务在游 戏 的其余部分中 支 配 它 们 。然后我们有以下内容476诉Gledel等人/理论计算机科学电子笔记346（2019）473Σ22连续性原理，其证明比控制博弈的相应原理简单得多[21]。注1.4（连续性原理）设G是一个图，A，B∈V（G）. 如果B∈A，则γMB（G|A）≤γM B（G|B）ndγMJB（G|A）≤γMJB（G|B）。事实上，这一评论来自这样一个事实，即支配者可以在G中应用相同的策略|A是G中的A|B.设γMB（G）<∞. 那么在支配者的任何获胜策略中，他将最多玩一半的顶点（因为Staller将玩另一半），又意味着1 ≤γMB（G）≤，，.（一）n（G）边界是尖锐的，例如考虑K1和K2的几个副本的不相交并。也很容易看出，通过考虑完全图的不交并和适当数量的K2手枪。类似地，对于S-对策，假设γMJB（G）∞，1≤γMJB（G）≤，（2）n（G）在那里所有的价值都可以实现。稍后我们将应用著名的ErdEscheros-Selfridge准则为Maker-Breaker游戏，内容如下。定理1.5（Erd-Selfridge准则[13]）如果F是一个超代数，则2−|一|<12 这是一个断路器的胜利。A∈F这个定理及其证明也可以在书[16，Theorem 2.3.3]中找到2Maker-Breaker控制数在这一节中，我们首先比较了γMB（G）和γMJB（G），并为所有可能的不变量值构造了图在第二部分中，我们比较了γMB（G）与控制数，并利用Erd-Selfridge准则发现了一类很大的图G，其中γMB（G）> γ（G）成立。2.1Maker-Breaker控制数在[4，21]中证明的关于控制对策的一个基本定理断言，当Domina-torstartsandwhenStallerstarts isboundedbyy1，也就是说，|γg（G）−γgJ（G）| ≤1对每个图G成立。下一个结果表明，制造者-破坏者控制数的情况是显着不同的。诉Gledel等人/理论计算机科学电子笔记346（2019）473477定理2.1若G是一个graph，则γ（G）≤γMB（G）≤γMJB（G）. 此外，对任意整数r，s，t，其中2 ≤r≤s≤t，存在图G使得γ（G）= r，γMB （G）=s，且ndγMJB（G）=t.注意，如果γ（G）= 1，则γMB（G）也= 1。因此，定理2.1不适用于r= 1的情况。另一方面，如果Gt（t≥ 1）是由t个不相交的三角形通过从每个三角形中确定一个顶点而得到的图（使得这个新顶点的度为2t），则γ（Gt）=1，γMB（Gt）=1，且γMJB（Gt）=t.定理2.1也可以推广到高连通图。为了理解这一点，考虑图Hk ， r ， s ， t，2≤r≤s≤t，k≥1，图1示意性地画出。1.一、这里，Kk团的每个顶点与团Kk + r的每个顶点相邻。可以看出，γ（Hk，r，s，t）=r，γM B（Hk，r，s，t）=s，并且dγMJB（Hk，r，s，t）=t。 更进一步，Hk，r，s，t是（k +1）-连通的.t−r+ 1s−r+ 1···KKKkKk···K KK KK...x1x2x3xr...xr+1xk +rKk+rFig. 1. 图Hk，r，s，t2.2与控制数的如前所述，γMB（G）= 1当且仅当γ（G）= 1。一般来说，刻画图G使得γMB（G）=γ（G）=k是有趣的，其中k≥2是固定整数。对于k= 2，答案很简单：命题2.2设G是一个图，γ（G）= 2。 则γMB（G）= γ（G）= 2当且仅当G有一个顶点位于G的至少两个γ-集合中.命题2.2也可以改写为对更大的k成立，但这或多或少只是改写了定义。更有趣的是找到相应图的结构特征。然而，这项任务似乎很困难。另一方面，Erd-Selfridge判据给出了γMB（G）> γ（G）的充分条件.设Xγ（G）是图G的γ-集的个数，参见. [9]的文件。然后又道：命题2.3若G是一个图且X γ（G）<2 γ（G）−1，则γMB（G）> γ（G）。考虑圈C3k−1，k≥1。已知且容易看出，γ（C3k−1）=K. 我们现在确定C3k−1的γ-集的个数。γ-集的每个顶点478诉Gledel等人/理论计算机科学电子笔记346（2019）473−23k 12支配着它自己和它的两个邻居由于图中有k个这样的三元组和3k−1个顶点，所以只有一个顶点被γ-集的两个顶点支配，所有其他顶点都被支配一次。如果两次被支配的顶点是固定的，那么圈的γ-集是唯一确定的。因为这个顶点有3k− 1个选择，所以我们有Xγ（C3k−1）= 3k− 1。 如果k≥5，则Xγ（C3k−1）= 3k− 1 2k−1 = 2γ（C3k−1）−1，根据命题2.3，我们得出结论：<γMB（C3k−1）>k=γ（C3k−1）。 实际上，γMB（C3k−1）比γg（C3k−1）正如我们将在第四节中看到的。命题2.3的逆命题并不成立，如下例所示。如果k∈{3，4}，则nXγ（C3k−1）=3k，−1>，2k−1=2γ（C3k−1）−1，但正如我们将在3残差图在这一节中，我们研究了一个构造上的Maker-Breaker控制数，这个构造可能是独立的，并且稍后将用于确定树的不变量。如果G是一个图，则我们说G的剩余图R（G）是通过迭代地去除悬垂路P2直到不存在这样的路而从G我们说P2是指P2有一条边附着在G因此，当这样的挂件P2被移除时，正好两个顶点和两条边被移除。当G=P2时，也可以去掉它，得到空图.注意，对于某个图G，H=R（G）当且仅当H是空图，H=K1，或者H的每个支撑顶点的度至少为3。 如果H没有支撑顶点，这一点尤其成立我们还注意到：引理3.1如果G是一个图，则R（G）是唯一的（直到同构）。如果R（G）/=K1，则G\V（R（G））是唯一的。 看到它 一般情况下不唯一，考虑一条路P2k+1，k≥2，以及不同的去除悬垂P2s的序列.引理3.2设G是一个图，R（G）是G的剩余图. 然后(i) G\V（R（G））是具有唯一完美匹配的森林，(ii) G有完美匹配当且仅当R（G）有完美匹配。为了证明本节的主要结果，我们还需要以下内容引理3.3如果T是一棵允许完美匹配的树，且v∈V（T），则Staller有一个S-对策策略，使得Dominator至少要选择n（T）支配T和v的顶点是由Staller在她的最后一步中使用的。证据我们证明了索赔的归纳n（T）。如果T=P2且v∈V（P2），则Staller可以在v上博弈，Dominator必须在另一个顶点上应答设n（T）≥4，T是根在任意顶点的BFS-树R. 设x是该BFS树的与r距离最大的叶子，设y是该BFS树的第4节，γ（C3k−1）=k k+1 ==γMB（C3k−1）。诉Gledel等人/理论计算机科学电子笔记346（2019）473479J222222x的邻居那么deg（y）= 2，因为T有完美匹配。设z是y的另一个邻居。设TJ=T\{x，y}。由于T有完美匹配，xy属于它，因此TJ也有完美匹配。如果v∈V（TJ），则Staller从y开始，Dominator必须在x上回复（否则Staller会赢），然后Staller将她的策略应用于TJ（根据归纳假设）。如果v∈ {x，y}，则她在T上应用策略，在z上采取最后一步，然后在最后一步采取v请注意，如果支配者在v上玩，而Staller在TJ上玩，则Staller赢得游戏，因为她可以阻止支配者在TJ中匹配的一对顶点上玩。根据Staller的上述策略，我们可以得出结论：Dominator的移动总数为n（T′）+1=n（T）。Q2 2请注意，根据引理3.3的证明策略，除非Staller想在叶子上玩，否则她会在支持顶点上玩，迫使Dominator在其相邻的叶子上回复，并将这个P2与图的其余部分定理3.4设R（G）是G的剩余图，H = G\V（R（G））. 然后(i) γJ（G）=n（H）+γJ （R（G）），MB2MB(ii)n（H）+ γMB（R（G））− 1 ≤γMB（G）≤n（H）+ γMB（R（G））.证据（i）H有完美匹配，根据引理3.2（i）是一个森林。设S-对策在G上进行，考虑Staller的以下策略。根据引理3.3，她可以在H的每一棵树上博弈，并且最后在这棵树的与R（G）相邻的顶点上博弈。统治者必须回答匹配（否则Staller赢得游戏）。因此，支配者（至少）在H上移动n（H）。此外，Staller在与R（G）相邻的顶点上进行博弈，因此在Staller在R（G）中进行第一步移动时，R 接下来，Staller是第一个移动在R（G）上，并在那里遵循她的最优策略，以确保至少γMJB（R（G））支配者的行动另一方面，统治者H或R（G），以及它在这个图上的策略。由于H有一个完美的匹配，支配者使得不超过n（H）在H上移动。更进一步说，他最多使γMJB（R（G））在R（G）上移动。因此，我们有γJ （G）=n（H）+γJ（R（G））。MB2MB(ii)现在假设D-博弈在G上进行。 为了证明上界，统治者由于H具有完美匹配，支配者在H上的移动不超过n（H）步。而且，他在R（G）上至多移动γMB（R（G））。 从而得到了上界γMB（G）≤n（H）+γMB（R（G））.为了证明下界，考虑Staller的以下策略，在支配者的第一步我们将区分两种情况，第二种情况有两个子情况，如图1所示二、1支配者的第一步是在R（G）上。Staller first将引理3.3中的策略应用到H的每棵树上，在每棵树上最后一步移动R（G）附近的顶点有了这个，480诉Gledel等人/理论计算机科学电子笔记346（2019）4732壳体2.1情况1y2 y1vX1x2d1壳体2.2图二、定理3.4证明中的情形的表示她迫使支配者在H上走（至少）n（H）步。之后我们有一个在R（G）上进行的普通D-博弈，所以如果Staller在那里遵循她的策略，那么支配者至少会在R（G）上走γMB步2 支配者的第一步是H。设d1为支配者第一步棋中的顶点，T为H中包含d1的连通分支（回想一下T是一棵树），P为T中d1和R（G）之间的最短路径，M为T的唯一完美匹配（参见图1）。引理3.2（i））。在这种情况下，Staller首先将引理3.3中的策略应用于H的所有其他树，将与R（G）相邻的顶点作为她在每棵树上的最后一步。接下来，Staller将引理3.3中的策略应用于M的边，这些边与P不相关。此外，她在最接近P的顶点上最后一个出场。在此之后，只有R（G）、P以及可能与P相邻的一些顶点保持非支配。2.1 至少有一个与P相邻的顶点仍然是非支配的（见图1）。2）。设 u 是 与 P 相 邻 的 非 支 配 顶 点。 Staller 在 P 上 使 用 它 的 邻 居 ，迫 使Dominator在u上回复。Staller在每个这样的顶点上都这样做。在此之后，唯一的非支配顶点位于P上，而且，到目前为止，从M开始的每个已经完全支配的边上至少有一次支配者的移动。只要P上M有更多的非支配边，其中至少有一条，比如e∈M，与P的一个Staller已经过的顶点s相关联。她的策略是在距离s为2的e的顶点上博弈。然后支配者必须在e的另一个顶点上回答，否则Staller通过使用它而获胜因此，Staller可以迫使Dominator回复所有剩余的边缘。HGD1T1R（G）TkT2···R（G）D1R（G）诉Gledel等人/理论计算机科学电子笔记346（2019）4734812222.2 H中唯一的非支配顶点位于P上。Staller支配者必须对v的一个邻居做出回应，否则v的一个邻居不是劣势的，Staller可以通过使用该顶点并创建双重威胁来获胜。事实上，在这种情况下，两个非支配的相邻顶点由Staller使用，无论Dominator在哪里回答，她都可以使用另一个连续的顶点并赢得比赛。设xi是P上沿d1方向距离v为i的顶点，yi是P上沿R（G）方向距v为i的顶点，对所有可能的i≥1，再次参见图2。如果支配者在x1上回复，那么Staller多米nator必须在y1时回复，否则Staller获胜。然后Staller重复这个策略，直到P是劣势的，即，她以递增的顺序在顶点y2k上进行游戏，而支配者被迫在y2k−1上进行回复。如果支配者在y1上回复，那么Staller在x2上回复。在那之后，多姆-我想玩x1。接下来，Staller采用了和之前相同的策略，将y1作为新的d1.在这两种情况下，支配者被迫在匹配M的每个边缘上至少走一步，因此在T上至少走n（T）步。在H-T上，根据引理3.3，至少有n（H-T）步。当T完全处于劣势时，Staller遵循她的最优策略，R（G）中的一个顶点u可能已经被支配（通过H中的支配者移动到R（G）附近）。 由于Staller但她可以想象支配者γMJB（R（G）|u）≥γMJB（R（G））|N[u]）≥γM B（R（G））−1，因此，在R（G）上的移动总数至少是γMB（R（G））−1。在这两种情况下，支配者至少走了n（H）+γMB（R（G））−1步，这证明了下界。Q注意，在不等式yγMJB（G|u）≥γMB（G）−1，则等式可由下式得到.例如，考虑图3中的图G。显然，γM B（G）=2且dγMJB（G|u）=1。u图3.第三章。 具有性质γM′B（G）的图G|u）=γM B（G）−1。如果G是一些具有完美匹配的树，其中至少有一个树与u相连，则我们得到图G的下界满足定理3.4（ii）。在本节的最后，我们应用剩余结构来确定树的Maker-Breaker控制数。这与支配博弈如果没有这样的结果是已知的，比照。[5、17、18]。482诉Gledel等人/理论计算机科学电子笔记346（2019）473n（T）;T有一个性能匹配，2n（T）−1;R（T）n=K1，n（T）−k+1;R（T）n=K1，k≥3，γMB（T）=222定理3.5如果T是树，则⎪2和否则，.n（T）; T具有完美匹配，γMJB（T）=2∞;否则。由定理3.5可知，树的γMB和γMJB是p多项式。4周期圈的D-对策控制数和S-对策控制数由以下公式给出：. ，n，− 1; n 3mod 4，J. ，n−1，−1;n 2mod 4，γg（Cn）=，n，;否则，γg（Cn）=，n-1，，否则为。这一基本结果最早是在一份未发表的手稿中得到的[20]。的这个结果首次出现在论文[19]中，并给出了另一种证明。对于完全控制对策，文献[10]也得到了类似的结果.后一篇文章只研究了路和圈上的完全控制博弈。因此，（总）博弈控制周期数远非简单明了。在这里，我们确定决策者-破坏者支配周期数，这是一个不太复杂的任务。使用引理1.1和事实1.2，很容易看出支配者在偶数周期上有一个获胜的策略。通过观察移除奇数圈的任何顶点的邻域使该图具有完美匹配，我们还可以看到Dominator在奇数圈上具有获胜策略。然而，有趣的是，Dominator不能比这些策略做得更好定理4.1如果n≥3，则γMB （Cn）=γMJB（Cn）=，n，.5总结发言最后，本文提出了Maker-Breaker控制数的几个问题和进一步研究(i) 对于（1）中的上界，我们提供了达到等式的图的例子。这些例子是没有联系的，这是不难实现的222诉Gledel等人/理论计算机科学电子笔记346（2019）473483偶数阶连通图的相等性然而，我们不知道任何奇阶连通图（与K1不同），使（1）中的等式得以实现。更一般地，我们要求关于（1）和（2）的极值图的特征(ii) 如前所述，如果图G满足γMB（G）=γ（G）=k，其中k≥2，那么寻找图G的结构特征是很有趣的是一个固定的整数。(iii) 研究γMB（GQH）和γMjB（GQH）也是一个有趣的问题，其中G和H是任意图，GQH是G和H的笛卡尔积.特别地，对于任意图G，确定γMB（PnQPm）（和γMjB（PnQPm））以及γMB（GQK2）（和γMjB（GQK2））是很有意义的.(iv) 如果G是一个余图，那么就不难确定是Dominator还是Staller赢得了Maker-Breaker控制博弈[12]。另一方面，在一项研究中，确定上图的Maker-Breaker控制数似乎并不简单。(v) 本文从支配者的观点出发，研究了Maker-Breaker控制数考虑Staller的观点也是引用[1] Beck，J.，[2] Bednars ka，M. 和T. L-uczak，Bias edpositionalgames forwhich randomst r egiesa renearlyoptimal，Combinatorica 20（2000）477-488.[3] Ben-Shimon，S.，M. Krivelevich和B. Sudakov，Local resilience and Hamilton maker-breaker games inrandom regular graphs，Combin.可能吧Comput. 20（2011）173[4] Br eBazar，B.，S. Kl avzar和D. F. Rall，统治游戏和想象力，SIAMJ. 离散数学24（2010）979-991。[5] Br eBazar，B.，S. Kl avzar和D. F. Rall，Dominationgameplay edontreesand spanningsubgraphs，DiscreteMath.313（2013）915-923.[6] Bujtas角，关于给定最小度图的博弈控制数，Electron.J.Combin。22（2015）#P3.29。[7] Clemens，D.，A. Ferber，M. Krivelevich和A. Liebenau，在随机棋盘上玩的制造者-破坏者游戏中的快速策略，Combin。可能吧Comput. 21（2012）897[8] Clemens，D. 和M. 我的朋友，如何快速C一个制造商赢得公平的偏见和游戏？离散数学 341（2018）51-66。[9] Connolly，S.，Z. Gabor，A.戈德博尔湾凯和T.Kelly，Bounds on the maximum number of minimumdominating sets，Discrete Math.339（2016）1537[10] Dorbec，P.和M. A. Henning，循环和路径的博弈完全支配，离散应用数学。208（2016）7[11] Dor bec，P.，G. Kosmrlj和G. Renault，Thedominancegameplay edonunionsof graphs，DiscreteMath.338（2015）71-79.484诉Gledel等人/理论计算机科学电子笔记346（2019）473[12] Du chene，E.， 诉Gledel，A. Parreau和G. Renault，Maker-B reaker dominationgame，arXiv：1807.09479[cs.DM]（2018年7月25日）.[13] 埃尔德斯特罗斯山口 和j. L. Selfridge，关于一个组合博弈，J. 复合二元理论系。 A14（1973）298-301。[14] Ferber，A.，M. Krivelevich和G. 随机回合制造者-破坏者博弈。图论85（2017）446[15] Hefetz，D.，M. Kri velevi ch，M. Sto ja kov i'candT. 萨布奥，在制造商和制造商的比赛中最后一次获胜。组合理论Ser.B 99（2009）39[16] Hefetz，D.，M. Kri velevi ch，M. Sto ja kov i'candT. Sza bo'，“Positional G ames”，Birkhauser/Springer，巴塞尔 ，2014年 。[17] Henning，M. A. 和C. 林文胜，林文胜. 数学图论37（2017）369[18] Henning，M. A.和D. F. Rall，具有相等全控制数和对策全控制数的树，离散应用。数学226（2017）58[19] K osmrlj，G.， 控制游戏的路径和周期，艺术数学。 温度 24（2017）125-136。[20] Kinnersley，W.B、D. B. West和R.Zemani，Game dominance for grid-like graphs，手稿，2012年。[21] Kinnersley，W. B、D. B. West和R.陈文，博弈控制数的极值问题，北京大学出版社，2001。离散数学27（2013）2090[22] Nadja fi-Arani，M. J.，M. Siggers和H. Soltani，具有平凡博弈控制数，J。Comb. Optim。32（2016）800[23] Schmidt，S.，弱S（K1，3）-自由森林的3/5-猜想，离散数学.339（2016）2767[24] 徐，K.，X. Li，S. Kl avzar，Ong raphs withlargestpossiblegamedominationnum ber，DiscreteMath.341（2018）1768-1777.
我的内容管理
展开
