Search

Cops and Robber is a well-studied two player pursuit-evasion game played on a graph. In this game, a set of cops, controlled by the first player, tries to capture the position of a robber, controlled by the second player. The cop number of a graph is the minimum number of cops required to capture the robber in the graph. A group of cops guard a subgraph if they can ensure that the robber cannot enter the subgraph without getting captured immediately. We study the applications of guarding to provide new bounds and improve existing bounds for several graph classes. In particular, we show that the cop number for butterfly networks and for solid grids is two. We also construct a partial grid with cop number 3 establishing that partial grids have same cop number as their superclass planar graphs. We also consider three well-studied variants of Cops and Robber : Cops and Fast Robber , Cops and Attacking Robber , and Surrounding CnR. We improve the existing bounds for the cop number of multidimensional grids for both Cops and Attacking Robber and Surrounding CnR. Finally, we consider Cops and Fast Robber on AT-free graphs to improve the existing bounds on the cop number for this game. [ABSTRACT FROM AUTHOR]

In this paper, we continue the study of the domination game on graphs introduced by Brešar et al. (2010). Haynes and Henning in 2009 introduced a paired-domination version of the domination game. We study an alternative paired-domination version of the domination game played on a graph G by two players, named Dominator and Staller. The players take turns choosing a pair of adjacent vertices of G such that neither vertex in the pair has yet been chosen and the vertices in the pair must dominate at least one vertex not dominated by the previously chosen vertices. This process eventually produces a paired-dominating set of vertices of G ; that is, a dominating set in G that induces a subgraph that contains a perfect matching. Dominator wishes to minimize the number of vertices chosen, while Staller wishes to maximize it. The game paired-domination number γ gpr (G) of G is the number of vertices chosen when Dominator starts the game and both players play optimally, and the Staller-start game paired-domination number γ gpr ′ (G) of G is the number of vertices chosen when Staller starts the game and both players play optimally. In this paper, we determine the paired-domination numbers γ gpr (G) and γ gpr ′ (G) when the graph G is a cycle. [ABSTRACT FROM AUTHOR]

We consider the connected game coloring number of a graph, introduced by Charpentier et al. as a game theoretic graph parameter that measures the degeneracy of a graph with respect to a connected version of the graph marking game. We establish bounds for the connected game coloring number of graphs of bounded treedepth and of k -trees. We also show that there exists an outerplanar 2-tree with connected game coloring number 5, which answers a question from Charpentier et al., (2020). [ABSTRACT FROM AUTHOR]

• Examined the effects of two naturalistic, game-based preschool math interventions • A CRT design examined the added value of a family math component for Head Start • Results indicated that the family math component added value to classroom math • For preschoolers age 50+ months, both interventions had significant effects • Number of math games played was significantly associated with higher math scores Differences in children's mathematics knowledge are evident at kindergarten entry, favoring children who have greater access to economic resources. Fostering preschoolers' mathematics learning at home and in classroom settings, through games and other developmentally appropriate activities, is of great interest to educators, early childhood leaders, and policymakers. This cluster randomized trial examined the effects of a naturalistic, game-based mathematics intervention implemented in Head Start classrooms and examined whether including a family math component added value. A total of 573 children (64% Hispanic; 60% multilingual) were included from 66 classrooms which were randomly assigned to Classroom Math (CM), Classroom Math + Family Math (CM+FM), or business-as-usual (BAU). Results indicated that the family math component did add value to the classroom-based intervention as CM+FM resulted in a significant positive impact on children's mathematics knowledge relative to BAU, but CM alone did not. For preschoolers age 50+ months, both interventions had significant effects on children's mathematics knowledge relative to BAU, but CM+FM had a stronger effect (d =.36). The number of math games played was significantly associated with higher mathematics scores and the number of family math mini-books returned had a significant impact on children's spring scores, over and above the number of games played. The CM+FM intervention also had a significant effect on teachers' instructional practice (d =.79). Adding a family math component to a game-based classroom intervention resulted in positive impacts for preschoolers and seems to be an effective, ecologically valid intervention that fosters early mathematical competencies. [ABSTRACT FROM AUTHOR]

In 2020, Costa et al. answered a long-standing open question, proposed by Bodlaender in 1991: the graph coloring game is PSPACE -complete. They also proved that the greedy coloring game, introduced by Havet and Zhu in 2013, is also PSPACE -complete. In 2019, Andres and Lock proposed five variants of the graph coloring game, which were proved PSPACE -complete by Lima et al. in 2022. In this paper, we extend these variants of the graph coloring game to the greedy coloring game and prove that all of them are PSPACE -complete, even if the number of colors is the chromatic number. Moreover, based on the connected variant of the graph coloring game proposed by Charpentier et al. in 2020, we introduce the connected greedy coloring game and prove that two natural variants of this game are PSPACE -complete. Despite this, we prove that in split graphs these two variants of the connected greedy coloring game are polynomial time solvable and we characterize the split graphs for which the associated connected game Grundy numbers are the minimum possible value (the chromatic number). Finally, we also characterize the split graphs which are bad, a notion introduced by Le and Trotignon in 2018 regarding connected greedy colorings. [ABSTRACT FROM AUTHOR]

Motivated by the success of domination games and by a variation of the coloring game called the indicated coloring game, we introduce a version of domination games called the indicated domination game. It is played on an arbitrary graph G by two players, Dominator and Staller, where Dominator wants to finish the game in as few rounds as possible while Staller wants just the opposite. In each round, Dominator indicates a vertex u of G that has not been dominated by previous selections of Staller, which, by the rules of the game, forces Staller to select a vertex in the closed neighborhood of u. The game is finished when all vertices of G become dominated by the vertices selected by Staller. Assuming that both players are playing optimally according to their goals, the number of selected vertices during the game is the indicated domination number, γ i (G) , of G. We prove several bounds on the indicated domination number expressed in terms of other graph invariants. In particular, we find a place of the new graph invariant in the well-known domination chain, by showing that γ i (G) ≥ Γ (G) for all graphs G , and by showing that the indicated domination number is incomparable with the game domination number and also with the upper irredundance number. In connection with the trivial upper bound γ i (G) ≤ n (G) − δ (G) , we characterize the class of graphs G attaining the bound provided that n (G) ≥ 2 δ (G) + 2. We prove that in trees, split graphs and grids the indicated domination number equals the independence number. We also find a formula for the indicated domination number of powers of paths, from which we derive that there exist graphs in which the indicated domination number is arbitrarily larger than the upper irredundance number. We provide some partial results supporting the statement that γ i (G) = n (G) / 2 if G is a cubic bipartite graph, and leave this as an open question. [ABSTRACT FROM AUTHOR]

Indicated coloring is a graph coloring game in which two players collectively color the vertices of a graph in the following way. In each round the first player (Ann) selects a vertex, and then the second player (Ben) colors it properly, using a fixed set of colors. The goal of Ann is to achieve a proper coloring of the whole graph, while Ben is trying to prevent the realization of this project. The smallest number of colors necessary for Ann to win the game on a graph G (regardless of Ben's strategy) is called the indicated chromatic number of G , denoted by χ i (G). In this paper, we show that for any graphs G and H , G [ H ] is k -indicated colorable for all k ≥ col (G) col (H). Also, we show that for any graph G and for some classes of graphs H with χ (H) = χ i (H) = ℓ , G [ H ] is k -indicated colorable if and only if G [ K ℓ ] is k -indicated colorable. As a consequence of this result, we show that if G ∈ G = { Chordal graphs, Cographs, Complement of bipartite graphs, { P 5 , C 4 } -free graphs, Connected { P 6 , C 5 , P 5 ¯ , K 1 , 3 } -free graphs which contain an induced C 6 , Complete multipartite graphs } and H ∈ F = { Bipartite graphs, Chordal graphs, Cographs, { P 5 , K 3 } -free graphs, { P 5 , p a w } -free graphs, Complement of bipartite graphs, { P 5 , K 4 , k i t e , b u l l } -free graphs, Connected { P 6 , C 5 , P 5 ¯ , K 1 , 3 } -free graphs which contain an induced C 6 , { P 5 , C 4 } -free graphs, K [ C 5 ] (m 1 , m 2 , ... , m 5) , Connected { P 5 , P 2 ∪ P 3 ¯ , P 5 ¯ , d a r t } -free graphs which contain an induced C 5 } , then G [ H ] is k -indicated colorable for every k ≥ χ (G [ H ]). This serves as a partial answer to one of the questions raised by A. Grzesik in Grzesik (2012). In addition, if G ∈ { Bipartite graphs, { P 5 , K 3 } -free graphs, { P 5 , p a w } -free graphs } and H ∈ F , then we show that χ i (G [ H ]) = χ (G [ H ]). [ABSTRACT FROM AUTHOR]

In the (s , d) -spy game over a graph G , k guards and one spy occupy some vertices of G and, at each turn, the spy may move with speed s (along at most s edges) and each guard may move along one edge. The spy and the guards may occupy the same vertices. The spy wins if she reaches a vertex at distance more than the surveilling distance d from every guard. This game was introduced by Cohen et al. (2016) [15] and is related to two well-studied games: Cops and Robber game and Eternal Dominating game. The guard number g n s , d (G) is the minimum number of guards such that the guards have a winning strategy (of controlling the spy) in the graph G. In 2018, it was proved that deciding if the spy has a winning strategy is NP-hard for every speed s ≥ 2 and distance d ≥ 0. In this paper, we initiate the investigation of the guard number in grids and in graph products. We obtain a strict upper bound on the strong product of two general graphs and obtain examples with King grids that match this bound and other examples for which the guard number is smaller. We also obtain the exact value of the guard number in the lexicographical product of two general graphs for any distance d ≥ 2. From the algorithmic point of view, we prove a positive result: if the number k of guards is fixed, the spy game is solvable in polynomial XP time O (n 3 k + 2) for every speed s ≥ 2 and distance d ≥ 0. In other words, the spy game is XP when parameterized by the number of guards. This XP algorithm is used to obtain an FPT algorithm on the P 4 -fewness of the graph. As a negative result, we prove that the spy game is W[2]-hard even in bipartite graphs when parameterized by the number of guards, for every speed s ≥ 2 and distance d ≥ 0 , extending the hardness result of Cohen et al. in 2018. • We obtain a strict upper bound for the guard number of the Spy Game on the strong product of two general graphs. • Spy Game is XP time solvable when parameterized by the number of guards for any speed and surveillance distance. • Spy game is W[2]-hard in bipartite graphs when parameterized by the number of guards for any speed and distance. [ABSTRACT FROM AUTHOR]

• We develop a novel model of pure risk-taking multi-period winner-take-all contest. • In our model, risk-taking behavior is disconnected from the standard risk preferences. • Our model admits a complete analytical solution for any finite number of periods. • Laboratory experiments reveal the role players' action space plays in risk-taking. • Our model is particularly relevant for R&D and employee promotion settings. We investigate a process of decision-making in a multi-period winner-take-all contest, in which competing players simultaneously choose among actions with different levels of risk every period. Strategic risk-taking is analyzed in isolation from effort choices, and, according to expected utility theory, risk preferences are irrelevant. We derive a closed-form solution of the dynamic game for any number of periods. In the equilibrium, a leading player chooses the lowest level of risk, a trailing player chooses the highest level of risk, and all elements of the action space with intermediate levels of risk are irrelevant. We design a laboratory experiment to test various comparative statics of the model and explore behavioral deviations. Our findings are consistent with theoretical predictions – subjects tend to choose riskier lotteries when they are behind and safer lotteries when they are ahead, while the magnitude of the advantage does not seem to affect the risk-taking levels. We also observe some behavioral deviations such as a decline in risk-taking in the absence of the safe option, which only occurs while being behind. We find the quantal response equilibrium of our dynamic game and explain some of behavioral deviations; incorporating learning, subject types, and the probability weighting function into the behavioral model allows us to explain the rest of behavioral findings obtained from the data and compare the relative importance of these components. [ABSTRACT FROM AUTHOR]

Given two graphs G and H , a size Ramsey game is played on the edge set of K N. In every round, Builder selects an edge and Painter colours it red or blue. Builder's goal is to force Painter to create a red copy of G or a blue copy of H as soon as possible. The online (size) Ramsey number r ˜ (G , H) is the number of rounds in the game provided Builder and Painter play optimally. We prove that r ˜ (C 4 , P n) ≤ 2 n − 2 for every n ≥ 8. The upper bound matches the lower bound obtained by J. Cyman, T. Dzido, J. Lapinskas, and A. Lo, so we get r ˜ (C 4 , P n) = 2 n − 2 for n ≥ 8. Our proof for n ≤ 13 is computer-assisted. The bound r ˜ (C 4 , P n) ≤ 2 n − 2 solves also the "all cycles vs. P n " game for n ≥ 8 – it implies that it takes Builder 2 n − 2 rounds to force Painter to create a blue path on n vertices or any red cycle. [ABSTRACT FROM AUTHOR]

The core of a transferable utility (TU) game, if it is not empty, is prescribed by the set of all stable allocations. The exact determination of the core reaches exponential time complexity. Therefore, its exact computation is often avoided as the number of players increases. In this work, we propose an estimator for the core of a TU game based on the statistical theory of set estimation. Concretely, we provide a core reconstruction that is obtained in polynomial time for general dimension. Additionally, convergence rates for the estimation error are derived. Finally, a consistent core-center estimator is established as a geometrical application of this methodology. • We estimate the core of TU games from set estimation theory. • The proposed algorithm has polynomial time complexity. • This procedure can be applied for TU games with arbitrary number of players. • As an application, an estimator of the core center is also introduced. [ABSTRACT FROM AUTHOR]

In the paper we introduce a new variant of the graph coloring game and a new graph parameter being the result of the new game. We study their properties and get some lower and upper bounds, exact values for complete multipartite graphs and optimal, often polynomial-time strategies for both players provided that the game is played on a graph with an odd number of vertices. At the end we show that both games, the new and the classic one, are related: our new parameter is an upper bound for the game chromatic number. [ABSTRACT FROM AUTHOR]

• Mother-child numeracy activities, but not father-child activities, were related to children's math interest. • Among four types of mother-child numeracy activities, number skill activities contributed the most to math interest. • Interest in mathematics predicted preschool children's later symbolic and non-symbolic number skills. An interest in mathematics has been found to be associated with mathematics performance among primary and secondary school children, but the antecedents and consequences of younger children's interest in mathematics have been less explored. The present study examined the role of parent-child numeracy activities in predicting young children's interest in mathematics and the relation between young children's interest in mathematics and their later mathematical skills. A sample of 105 preschool children in Hong Kong were recruited and assessed at two time points: the second year of preschool and half a year later in the third year. The results showed that four types of mother-child numeracy activities – number skill, number book, number game, and number application activities –were associated with children's interest in mathematics concurrently. Among the four types, number skill activities contributed the most. However, none of the father-child numeracy activities were found to predict children's interest in mathematics. Moreover, children's interest in mathematics related to the later development of their symbolic and non-symbolic number skills after the initial levels of number skills were controlled. Our findings highlight the possible role of mother-child numeracy activities in fostering young children's interest in mathematics and the contribution of this interest to later number skills. [ABSTRACT FROM AUTHOR]

• Proved several lower and upper bounds on the Voronoi games on simple and convex polygons. Almost all are tight. • Devised optimal strategies for the games on convex polygons in poly-log linear and linear time for the players. • Extended the results on the bounds on the Voronoi games on polyhedra in R 3. • Polynomial-time strategies for both the players are devised for Voronoi games on convex polyhedra with restrictions. • Computed common intersection of ellipses in O (n log ⁡ n) time. The competitive facility location problem is the problem of determining facility locations involving multiple players to optimize their various gains. The Voronoi game is a competitive facility location problem on a given arena played by two players, the server and the adversary. The players alternately take turns, one or more times, to place their facilities in the arena with a predetermined set of n clients , where both facilities and clients are denoted by points, to maximize some resource gain. The Voronoi game on a polygon P is a type of competitive facility location problem where n clients are located on the boundary of P. The server, Alice, and adversary, Bob, are respectively in the interior and the exterior of the polygon P at locations A and B , respectively. Additionally, the metrics for Alice and Bob are the internal and external geodesic distances for the polygon P , respectively. In this paper, we present some surprising results on the Voronoi games on polygons. We prove lower and upper bounds of ⌈ n / 3 ⌉ and n − 1 respectively in the single-round game for the number of clients won by the server for n clients. Both bounds are tight. In the process, we show that in some convex polygons, the adversary wins no more than k clients in a k -round Voronoi game for any k ≤ n. Consequentially, the adversary Bob does not have a guaranteed good winning strategy even for the simpler case of convex polygons, i.e., there exist convex polygons such that no placement of B guarantees more than k clients in the k -round game. We also design O (n log 2 ⁡ n + m log ⁡ n) and O (n + m) time algorithms to compute the optimal locations for the server and the adversary respectively to maximize their client counts where the convex polygon has size m. Moreover, we present an O (n log ⁡ n) time algorithm to compute the common intersection of a set of n ellipses. This is needed in our algorithm and may be of independent interest. Lastly, we present some results on the Voronoi games, where the arena is a convex polytope. The server and adversary are respectively in the interior and exterior of P , and the clients are on the polytope boundary. [ABSTRACT FROM AUTHOR]

This paper provides a classification of all monotonic bipartite simple games. The problem we deal with is very versatile since simple games are inequivalent monotonic Boolean functions, functions that are used in many fields such as game theory, neural networks, artificial intelligence, reliability or multiple-criteria decision-making. The obtained classification can be implemented in an algorithm able to enumerate bipartite simple games. These numbers provide some light on enumerations of several subclasses of bipartite simple games, for which we find formulas. Complete simple games, a subclass of all simple games for which the desirability relation is a complete preordering, were already classified by means of two parameters: a vector and a matrix fulfilling some conditions. Complete simple games are inequivalent monotonic regular Boolean functions. In this paper, we deduce a procedure for bipartite non-complete games, which allows enumerating the number of bipartite simple games. Several formulas are obtained, in particular polynomial expressions for the number of bicameral meet games and the number of bicameral join games, two types of voting systems widely used in practice. [ABSTRACT FROM AUTHOR]

It is conjectured that the game domination number is at most 3 n ∕ 5 for every n -vertex graph which does not contain isolated vertices. It was proved in the recent years that the conjecture holds for several graph classes, including the class of forests and that of graphs with minimum degree at least two. Here we prove that the slightly bigger upper bound 5 n ∕ 8 is valid for every isolate-free graph. [ABSTRACT FROM AUTHOR]

The graph coloring game is a two-player game in which, given a graph G and a set of k colors, the two players, Alice and Bob, take turns coloring properly an uncolored vertex of G , Alice having the first move. Alice wins the game if and only if all the vertices of G are colored. The game chromatic number of a graph G is then defined as the smallest integer k for which Alice has a winning strategy when playing the graph coloring game on G with k colors. In this paper, we introduce and study a new version of the graph coloring game by requiring that the starting graph is connected and, after each player's turn, the subgraph induced by the set of colored vertices is connected. The connected game chromatic number of a connected graph G is then the smallest integer k for which Alice has a winning strategy when playing the connected graph coloring game on G with k colors. We prove that the connected game chromatic number of every connected outerplanar graph is at most 5 and that there exist connected outerplanar graphs with connected game chromatic number 4. Moreover, we prove that for every integer k ≥ 3 , there exist connected bipartite graphs on which Bob wins the connected coloring game with k colors, while Alice wins the connected coloring game with two colors on every connected bipartite graph. [ABSTRACT FROM AUTHOR]

• Overview of (ultra)high-throughput screening assay technologies. • Focus on sample throughput for measuring enzyme activity, substrate scope, and stability to process conditions. • Functional screening methods for biocatalysts from various enzyme classes. • Emphasis on development of universal assay strategies. • Novel screening protocols for microfluidic cell or droplet sorting. The booming demand for environmentally benign industrial processes relies on the ability to quickly find or engineer a biocatalyst suitable to ideal process conditions. Both metagenomic approaches and directed evolution involve the screening of huge libraries of protein variants, which can only be managed reasonably by flexible platforms for (ultra)high-throughput profiling against the desired criteria. Here, we review the most recent additions toward a growing toolbox of versatile assays using fluorescence, absorbance and mass spectrometry readouts. While conventional solution based high-throughput screening in microtiter plate formats is still important, the implementation of novel screening protocols for microfluidic cell or droplet sorting systems supports technological advances for ultra-high-frequency screening that now can dramatically reduce the timescale of engineering projects. We discuss practical issues of scope, scalability, sensitivity and stereoselectivity for the improvement of biotechnologically relevant enzymes from different classes. [ABSTRACT FROM AUTHOR]

In this paper, we answer a long-standing open question proposed by Bodlaender in 1991: the game chromatic number is PSPACE-hard. We also prove that the game Grundy number is PSPACE-hard. In fact, we prove that both problems (the graph coloring game and the greedy coloring game) are PSPACE-Complete even if the number of colors is the chromatic number. Despite this, we prove that the game Grundy number is equal to the chromatic number for split graphs and several superclasses of cographs, extending a result of Havet and Zhu in 2013. [ABSTRACT FROM AUTHOR]

We consider the computational complexity of reconfiguration problems, in which one is given two combinatorial configurations satisfying some constraints, and is asked to transform one into the other using elementary operations, while satisfying the constraints at all times. Such problems appear naturally in many contexts, such as model checking, motion planning, enumeration, sampling, and recreational mathematics. We provide hardness results for problems in this family, in which the constraints and operations are particularly simple. More precisely, we prove the PSPACE -completeness of the following decision problems: • Given two satisfying assignments of a planar monotone instance of NAE 3-SAT, can one assignment be transformed into the other by a sequence of variable flips such that the formula remains satisfied at every step? • Given two subsets of a set S of integers with the same sum, can one subset be transformed into the other by adding or removing at most three elements of S at a time, such that the intermediate subsets also have the same sum? • Given two points in { 0 , 1 } n contained in a polytope P specified by a constant number of linear inequalities, is there a path in the n -hypercube connecting the two points and contained in P ? These problems can be interpreted as reconfiguration analogues of standard problems in NP. Interestingly, the sets of instances that appear as input to the reconfiguration problems in our reductions lie in P. In particular, the elements of S and the coefficients of the inequalities defining P can be restricted to have logarithmic bit-length. [ABSTRACT FROM AUTHOR]

In this paper, we address an instance of uniquely solvable mean-field game with a common noise whose corresponding counterpart without common noise has several equilibria. We study the selection problem for this mean-field game without common noise via three approaches. A common approach is to select, amongst all the equilibria, those yielding the minimal cost for the representative player. Another one is to select equilibria that are included in the support of the zero noise limit of the mean-field game with common noise. A last one is to select equilibria supported by the limit of the mean-field component of the corresponding N -player game as the number of players goes to infinity. The contribution of this paper is to show that, for the class under study, the last two approaches select the same equilibria, but the first approach selects another one. [ABSTRACT FROM AUTHOR]

2-Coloring number is a parameter, which is often used in the literature to bound the game chromatic number and other related parameters. However, this parameter has not been precisely studied before. In this paper we aim to fill this gap. In particular we show that the approximation of the game chromatic number by the 2-coloring number can be very poor for many graphs. Additionally we prove that the 2-coloring number may grow quadratically as a function of the maximum degree of a graph, whereas the game chromatic number is always at most linear. Moreover, we establish the values of the 2-coloring number for several graph classes, such as complete k -partite graphs, cacti and thorny graphs, trees and subcubic graphs. It is shown that in all these cases one may compute the exact value in a polynomial time. [ABSTRACT FROM AUTHOR]

Evolutionary games with a finite number of players may manifest transient oscillatory dynamics before reaching an absorbing state. Such oscillations could be prone to synchronization, however its details and specific properties are not known. Here, we investigate synchronization of metastable oscillations in the finite-dimensional evolutionary game "Battle of the Sexes", as well as the possibility of controlling the properties of these oscillations by a multiplicative periodic signal. The appropriately generalized frequency and phase quantifiers demonstrate the possibility of synchronization, and the asymmetry of frequency range, induced by the finite size of population. Evolution of oscillations under strengthening periodic driving depends on whether synchronization is reached: in the synchronous regime the amplitude of oscillations grows, while their lifetime decreases, whereas in the asynchronous regime their amplitude decays to zero with the quasi-stationary distribution becoming unimodal. • Metastable oscillations observed in the evolutionary game "Battle of the Sexes". • In a game with modulated payoffs, synchronization of oscillations is observed. • The synchronization area depends on the population size and modulation amplitude. • For small-size populations the frequency locking interval is strongly asymmetric. • Properties of metastable oscillations change in synchronous and asynchronous modes. [ABSTRACT FROM AUTHOR]

Given a graph G and an integer k , two players take turns coloring the vertices of G one by one using k colors so that neighboring vertices get different colors. The first player wins if at the end of the game all the vertices of G are colored. The game chromatic number χ g (G) is the minimum k for which the first player has a winning strategy. In this study, we prove that the game chromatic number of the splitting graphs of the path P n and cycle C n for n ≥ 5 is 4. We also answer a question posed by Xuding Zhu in [12] for the splitting graphs of path P n and n -cycle for all n ≥ 3 [ABSTRACT FROM AUTHOR]

Abstract A seminal result by Nordhaus and Gaddum states that 2 n ≤ χ (G) + χ (G ¯) ≤ n + 1 for every graph G of order n , where G ¯ is the complement of G and χ is the chromatic number. We study similar inequalities for χ g (G) and c o l g (G) , which denote, respectively, the game chromatic number and the game coloring number of G. Those graph invariants give the score for, respectively, the coloring and marking games on G when both players use their best strategies. [ABSTRACT FROM AUTHOR]

Abstract Developing adaptive expertise with arithmetic problem solving is a much desired aim of primary school mathematics education. However, there are very few practical tools for teachers that would aid reaching this complex mathematical learning goal. The aim of the present study was to test the effects of a game-based learning environment in supporting primary school students' adaptive number knowledge and related arithmetic skills. Participants were 1168 students in grades four, five, and six. Classes were randomized in two conditions: in the experimental group regular mathematics teaching was enriched with gameplay using the Number Navigation Game (NNG), and in the control group students continued according to their regular math curriculum. An experimental design with pre- and post-test was used to measure students' adaptive number knowledge, arithmetic fluency, and pre-algebra knowledge. Overall, results showed that the experimental group outperformed the control group on adaptive number knowledge and math fluency. Results showed varying effects of the training in different grade levels, with more pronounced improvement of students' adaptive number knowledge in grade five. Game performance was related to the experimental group's post-test scores even after controlling for pre-test scores and grade. Results suggest that the NNG is effective in enhancing different types of arithmetic skills and knowledge in different grades of primary school education and can provide teachers with a practical and flexible tool to extend their regular classroom practice. Highlights • Game-based intervention for training adaptive number knowledge was used. • Results showed a positive impact on adaptive number knowledge. • The intervention had varying effects across different grades. • Game performance was related to the increase of math learning outcomes. • Adaptive number knowledge can be enhanced by the Number Navigation Game. [ABSTRACT FROM AUTHOR]

Various forms of sorting problems have been studied over the years. Recently, two kinds of sorting puzzle apps have gained popularity. In these puzzles, we are given a set of bins filled with colored units, balls or water, and some empty bins. These puzzles allow us to move colored units from a bin to another when the colors involved match in some way or the target bin is empty. The goal of these puzzles is to sort all the color units in order. We investigate computational complexities of these puzzles. We first show that these two puzzles are essentially the same from the viewpoint of solvability. That is, an instance is sortable by ball-moves if and only if it is sortable by water-moves. We also show that every yes-instance has a solution of polynomial length, which implies that these puzzles belong to NP. We then show that these puzzles are NP-complete. For some special cases, we give polynomial-time algorithms. We finally consider the number of empty bins sufficient for making all instances solvable and give non-trivial upper and lower bounds in terms of the number of filled bins and the capacity of bins. [ABSTRACT FROM AUTHOR]

Algorithmic thinking is a core skill for constructing algorithms to solve problems and for understanding computer science. The purpose of this study was to examine the effects of using game mechanics and a student-generated questions strategy to promote algorithmic thinking skills in an online puzzle-based game learning system. An online puzzle-based game learning system, TGTS (Turtle Graphics Tutorial System), was developed to help students learn algorithmic thinking skills by allowing them to solve puzzles. A quasi-experiment was conducted to examine the effectiveness of using game mechanics alone and using game mechanics plus a student-generated questions strategy. Nine fourth-grade elementary classes (n = 242) were used to form three treatment groups, including one without game mechanics, one using game mechanics, and one using game mechanics plus a student-generated questions strategy. The results indicate that TGTS with game mechanics significantly enhanced algorithmic thinking skills and puzzle-solving performance. Furthermore, although TGTS with game mechanics plus the student-generated questions strategy is less effective than TGTS with only game mechanics in puzzle solving, it is in fact more effective in enhancing the algorithmic thinking skills. Additionally, this study demonstrated that TGTS with game mechanics plus the student-generated questions strategy can enhance students' engagement experiences and willingness to participate. This study can be a reference for designing learning activities and developing an online puzzle-based game learning system to promote students’ learning of algorithmic thinking skills. [ABSTRACT FROM AUTHOR]

Either for recreational or professional reasons, ships travel across the globe generating a network of maritime traffic with routes connecting key areas such as ports, off-shore facilities or fishing areas. Monitoring vessels' position relatively to maritime routes provides crucial information about their destination, and can help reducing the risk of collision. In this paper, we implement a fuzzy logic approach for associating vessels to maritime routes, suitable to variable surveillance contexts and very sparse data. Moreover, the framework is agnostic to the way maritime routes are provided, either reflecting patterns-of-life from statistical models extracted from real data or being hand-crafted by a user. Fuzzy membership functions enable expressing that vessels can belong more or less to route corridors, while they follow only one of the possible routes. The computation of membership scores relies on a precise distance computation involving geometrical properties of Earth, valid for very large route segments. The defuzzification step allows non-specific outputs. Several instantiations with aggregation operators of different semantics are compared on a real dataset of tracklets from the Automatic Identification System, with ground truth labels of routes. The performance is assessed in a quality space along with the three dimensions of correctness , specificity and confidence. • We propose a geometry-based fuzzy approach for vessel-to-route association. • Earth geometrical properties are considered in the definition of membership functions. • The proposed approach is valid for very large maritime route segments without data. • This method works equally for routes generated from data and handcrafted by users. • Performance is assessed in a quality space along correctness, specificity, confidence. [ABSTRACT FROM AUTHOR]

The literature of games in education has a rich and multidisciplinary content. Due to the large number of studies in the field, it is not easy to analyze all relevant studies. There are few studies exploring the big picture of research trends in the field. For this reason, the purpose of this study is to examine longitudinal trends of game-based research in education using text mining techniques. 4980 publications were retrieved as an experimental dataset indexed by the SCOPUS database in the period 1968 to mid-2021. The results include descriptive statistics of game-based research, trends of the research topics, and trends in the frequency of each topic over time. They show that the number of studies focusing on the use of games in education has increased, particularly since the 2000s when Internet use accelerated and became widespread. Approximately 70% of all the studies were conducted in the last 10 years. One third of the studies is related to the main topic of game-based learning. It is significant that in the last three decades the topic of serious games has been among the top three trends. Considering usage acceleration of the topics, the highest values belong to game-based learning, serious games and student science games, in that order. The findings of this study are expected to guide the field by providing a better understanding of the trends of games in education and offer a direction for future research. • Increase in the number of game researches in the last two decades was explored. • Transition to Serious Educational Games and Game-based Learning Terms was seen. • Increase in the number of games developed in science and physical education was explored. • Insufficient number of robust and longitudinal researches was obtained. • The key purpose of the study is to reveal the trends and changes in game in education. [ABSTRACT FROM AUTHOR]

Research has shown that difficulty adaptation is a promising instructional technique in digital game-based learning. Nevertheless, although the strength and direction of difficulty adaptation can affect motivational outcomes, these effects remain insufficiently examined in game-based learning. This within-subject study examined how the strength and direction of difficulty adaptation affected motivational outcomes in digital game-based math learning. The participants were 167 Finnish fifth-graders who studied fractions with the Number Trace game. The game included 144 tasks, half were adapted according to participants' playing performance. Situational interest and perceived difficulty were measured several times with in-game self-report items during the intervention. The manipulation check confirmed that difficulty adaptation was implemented successfully as task correctness and perceived difficulty changed according to the strength and direction of adaptation. Regarding motivational outcomes, two-way repeated-measures ANOVAs showed that the difficulty adaptation increased situational interest, but only when the task difficulty was substantially adapted downwards. Contrary to our expectations, a substantial upwards adaptation of the task difficulty significantly decreased situational interest. Minor adaptation of difficulty did not affect situational interest. The current study contributes to the field of adaptive digital learning environments by highlighting the effects of the strength and direction of difficulty adaptation on motivational outcomes. Theoretical, practical, and methodological implications of the findings are discussed. • Repeated in-game measurements captured temporal changes of situational interest. • Difficulty adaptation affected perceived difficulty as expected. • The strength and direction of difficulty adaptation affected situational interest. • Only substantial adaptation of difficulty affected situational interest. • Changes in task difficulty led to inverse changes in situational interest. [ABSTRACT FROM AUTHOR]

This study examines the factors influencing thermal comfort in urban squares of India. Four designed squares dominated by recreational cum commercial activities were studied during summer. The study establishes that comfort is a finely graded perceptual construct determined by a multitude of factors. Relative weightages of varied factors influencing thermal comfort are determined using structural equation modelling (SEM). In addition to the perceived micrometeorological conditions, socio-demographic factors, prior thermal history as well as perception pertaining to varied open space attributes (e.g. environmental features, spatial, aesthetics aspects) were examined. 409 valid responses were collated from the chosen squares and used for formulating the path model. The perception of open space attributes (e.g. environmental features; spatial and aesthetic aspects) had a comparatively higher effect on subjective thermal comfort assessment. Among the open space attributes, perception of environmental features was the most decisive factor. The findings of the study provide valuable insight for improving the thermal environment of urban squares. • Path model formulated to present factors influencing outdoor thermal comfort. • Relative weightages of factors influencing outdoor thermal comfort determined. • Perception of site attributes decisively influences thermal comfort outdoors. • Environmental features have a stronger influence on thermal comfort than other factors. [ABSTRACT FROM AUTHOR]

The graph coloring game is a two-player game in which the two players properly color an uncolored vertex of G alternately. The first player wins the game if all vertices of G are colored, and the second wins otherwise. The game chromatic number of a graph G is the minimum integer k such that the first player has a winning strategy for the graph coloring game on G with k colors. There is a lot of literature on the game chromatic number of graph products, e.g., the Cartesian product and the lexicographic product. In this paper, we investigate the game chromatic number of the strong product of graphs, which is one of major graph products. In particular, we completely determine the game chromatic number of the strong product of a double star and a complete graph. Moreover, we estimate the game chromatic number of some King's graphs, which are the strong products of two paths. [ABSTRACT FROM AUTHOR]

A polyomino is a shape best described as a connected set of cells in the square lattice. As part of recreational mathematics, polyominoes have seen active research since the 1950s. Simultaneously, polyominoes have been investigated in statistical physics under the name "lattice animals," mainly in regards to percolation problems. One of the main points of interest is to solve the yet unanswered question of how many different polyominoes exist. Most of the focus, so far, went to estimating the number of different polyominoes that can be made with a given fixed number of cells. Recently, there are increased efforts to discover the number of polyominoes with not only a given area, but with a given perimeter size or perimeter defect as well. Roughly speaking, the perimeter defect is a number that measures how many twists a polyomino has. Formally, the defect of a polyomino P is defined as the deviation of the perimeter size of P from the maximum possible perimeter size taken over all polyominoes of the same area as P. Interestingly, a polyomino might contain a column or row which can be "cut" out of the polyomino, then the remaining parts of the polyomino are "glued" back together along the cut, and result in a smaller polyomino with equal perimeter defect to the original. By repeating such "cut-and-glue" operations on a polyomino until all matching columns and rows have been removed, one obtains a so-called "reduced polyomino." We expand on the efforts regarding perimeter defect and reduced polyominoes, in two directions. First, given a fixed perimeter defect, we demonstrate and prove upper and lower bounds on the width and height, as well as an upper bound on the area, of any reduced polyomino with a given perimeter defect. Second, we present an algorithm for enumerating all reduced polyominoes with a given perimeter defect, and calculate their combined generating function. From the generating function, we can extract a formula A (k) (n) for the number of polyominoes that have the fixed perimeter defect k and area n , for any n. Using our new algorithm, and in the case of k = 5 some additional manual calculations, we provide closed formulae of A (k) (n) , for up to k = 5 , as well as the generating functions for up to k = 5. This is an improvement over the previously known formulae, which were known only up to k = 3. [ABSTRACT FROM AUTHOR]

The study examined effects of playing number games (linear number board game, circular number board game, and nonlinear numerical activities) on the development of number knowledge and early arithmetic. A passive control group was also included in the design. 114 5-year-old preschool children participated. Four tasks (number line estimation, counting, naming Arabic numbers, and arithmetic calculation) were used as dependent measures. Children assigned to an intervention participated in six 10-min sessions during a period of three weeks. Children playing the linear number board game improved their performance on the number line estimation task, while children playing the other games did not. Furthermore, children playing the linear number board game showed a substantial enhancement of their calculation performance. The positive effects of playing linear number board games support the representational mapping hypothesis. The finding concerning calculation provides support to the assumption that a linear representation is important for early arithmetical learning. [ABSTRACT FROM AUTHOR]

Abstract: The pandiagonal Latin squares constructed using Hedayat’s method are cyclic. During the last decades several authors have described methods for constructing pandiagonal Latin squares which are semi-cyclic. In this paper we propose a recursive method for constructing non-cyclic pandiagonal Latin squares of any given order , where is a positive composite integer not divisible by 2 or 3. We also investigate the orthogonality properties of the constructed squares and extend our method to construct non-cyclic pandiagonal Sudoku. [Copyright &y& Elsevier]

Brazil is currently facing one of the worst environmental crises in history. The over-exploitation of natural resources, unrestrained expansion of fisheries, and mostly ineffective conservation policies impose great difficulty in regulating and supervising fishing activities, whether commercial or recreational. Unreported and unregulated recreational fisheries are largely carried out along the Brazilian coast; however, their potential for exploitation of fish stocks remain unknown. To obtain data regarding this popular and poorly known leisure activity, we compiled information on catches posted by recreational anglers on a social media platform between 2008 and 2013. Photographic records of fish caught on the continental shelf off the southern Atlantic Ocean in Brazil were downloaded and assessed, and species were identified and quantified (trophies and total captures) for each fishing trip (day), including the number of anglers, totaling 788 fishing days, with an average of 4.2 anglers/day. A total of 50 species were recorded: eight elasmobranchs and 42 teleosteans. Regarding conservation status, 25 species were categorized as threatened (25.5%) and one as data deficient (25.5%) at the global level according to the International Union for Conservation of Nature. Notably, elasmobranchs, dolphinfishes, bluefishes, croakers, triggerfishes, Atlantic bigeyes, and sharks showed high capture frequencies. Our results indicate the need for an efficient system to monitor recreational fishing, as well as co-management plans discussed with all stakeholders to control and reduce the worrying rate of capture of threatened species. • Unreported and unregulated fisheries are largely carried out along the Brazilian coast. • Social media platforms can be a complementary tool to obtain (local and nationwide) data on endangered species. • Estimated catches of threatened species were substantial, especially elasmobranchs. • Participatory research has also become a crucial ally in data collection and ca be associated with fishing monitoring. [ABSTRACT FROM AUTHOR]

Abstract: The sudoku completion problem is a special case of the latin square completion problem and both problems are known to be NP-complete. However, in the case of a rectangular hole pattern–i.e. each column (or row) is either full or empty of symbols–it is known that the latin square completion problem can be solved in polynomial time. Conversely, we prove in this paper that the same rectangular hole pattern still leaves the sudoku completion problem NP-complete. [Copyright &y& Elsevier]

Abstract: We compared the learning from playing a linear number board game of preschoolers from middle-income backgrounds to the learning of preschoolers from low-income backgrounds. Playing this game produced greater learning by both groups than engaging in other numerical activities for the same amount of time. The benefits were present on number line estimation, magnitude comparison, numeral identification, and arithmetic learning. Children with less initial knowledge generally learned more, and children from low-income backgrounds learned at least as much, and on several measures more, than preschoolers from middle-income backgrounds with comparable initial knowledge. The findings suggest a class of intervention that might be especially effective for reducing the gap between low-income and middle-income children''s knowledge when they enter school. [Copyright &y& Elsevier]

• Urgent sustainability transformations will change urban dwellers' daily lives. • Experimental futures approaches can generate a range of sustainable urban futures. • We developed and tested an experimental urban sustainability game. • Players engage with built environment, knowledge exchange and large-scale visioning. • This approach enables citizens to collectively imagine relevant, inspiring futures. The urban sustainability transformations that are urgently needed will have significant effects on the daily lives of city dwellers. As ways to imagine and co-design sustainable urban futures, experiments within the present-day urban environment are increasingly popular. This paper investigates how such an experimental approach can serve as the base of an applied urban futures game that enables its players to reflect on and imagine ways to address complex sustainability problems. We developed a large-scale mobile urban futures game, Utrecht2040, that provides its players with sustainability content, reflection, and motivation for action. The digital infrastructure of the game and large number of players provided unique opportunities for measuring outcomes. Our results indicate that this type of experimental gaming offers a new way for players to collect existing sustainable practices or 'seeds', and use them to collectively create glimpses into relevant sustainable urban futures. At the individual player level participants reported an increased understanding of sustainability and motivation to act. We conclude that large-scale collective experimental futures games in socio-spatial urban environments are a high-potential avenue for overcoming the "crisis of the imagination" by creating inclusive urban futures that inspire action. [ABSTRACT FROM AUTHOR]

Digital camera monitoring data on recreational boating traffic are often manually interpreted and the reading cost can be expensive. Typically, these data are used along with other periodic survey information and camera data between these surveys may not be read, creating gaps in the time series. We predicted recreational boating traffic during these 'gap' periods using historical camera data and covariates to complete the time series data. Predictive models were built in a Bayesian regression modelling framework to determine the daily distribution of recreational boating traffic at two ramps in Western Australia based on climatic variables (temperature, humidity, wind speed, direction and gust, and sea level pressure) and some temporal classifications (month and day type). Two observed year-long datasets of boating traffic were used, with a year-long gap between them. One set was used to build models, and the other set was used for validation purposes. Models were developed using leave-one-out cross-validation, and ensemble prediction. Fitted models explained 50% [95% credible interval (CI) of R 2 : 0.40–0.58] and 62% [95% CI of R 2 : 0.58–0.66] of the variabilities in the daily number of boat launches at the two ramps. Subsequently, using data for the preceding period where camera data were read, we imputed plausible estimates for the period between readings. Imputed values generally aligned well with the observed data, with some temporal biases at the bulk and upper tail of the distributions. The 95% credible intervals adequately reflected the observed data at both ramps. Data for the constructed periods depicted the general trends for the observed periods. Our results provide useful insights into using climatic factors to predict boating traffic to 'fill in the gaps' between survey years which could assist in the ongoing monitoring to promote sustainable management of recreational fisheries. • Data on boating traffic often missing in between surveys, creating gaps in time series. • Bayesian regression modelling framework adequately described plausible distribution for missing periods. • Imputed values for missing periods aligned well with data for observed periods. • Relevant auxiliary information can provide support for continuous monitoring of recreational boating traffic. [ABSTRACT FROM AUTHOR]

We highlight important steps that researchers should follow when using social media data, in particular when the aim of their research is to characterize illegal fishing. Specifically, we provide a checklist of mitigation strategies focusing on data privacy concerns and ethical principles associated with human-subject research. We hope our reflections will contribute to a more responsible use of social media and other digital platforms among marine conservation scientists. [ABSTRACT FROM AUTHOR]