0
votes
2answers
114 views

Real world application of dominating set?

can anyone tell me about the application of vertex coloring problem and algorithm for vertex color problem in graph or networks.
13
votes
3answers
3k views

The Best Strategy and Highest Possible Score for the “Threes!” Game.

[There's still the strategy to go. A suitably robust argument that establishes what is statistically the best strategy will be accepted.] Here's my description of the game: There's a $4\times 4$ ...
2
votes
2answers
128 views

Winning a restricted game of Nim?

Given the following piles, find the Grundy number of the initial position and make the first move in a winning strategy given that no more than two sticks may be removed from a pile at any time. Pile ...
1
vote
1answer
61 views

Determining Grundy Numbers for an inverted takeaway game

Given the following game, I need to determine a winning strategy and find the set of positions in the kernel. I figure the best way to do so would be with Grundy numbers. Rules: The game consists ...
12
votes
2answers
310 views

Determining the number of valid TicTacToe board states in terms of board dimension

I am attempting to find a closed form equation in terms of $n$, for the number of valid Tic-Tac-Toe board states (ignoring symmetry), where the board has dimension $n \times n ,\; 0 \lt n,\;n \in \Bbb ...
4
votes
1answer
96 views

Finding maximum score in a “bubble pop” game

Consider the following game: there is a n×n field, where each cell is randomly coloured in one of m colours. Let a group of cells be a set of same-coloured cells s.t. every cell in a group has at ...
6
votes
1answer
119 views

Invariance of strategy-proof social choice function when peaks are made close from solution

A question emerging from reading Schummer, J., & Vohra, R. V. (2002). Strategy-proof Location on a Network. Journal of Economic Theory, 104(2), 405–428. The setting is as follows: A finite set ...
1
vote
0answers
114 views

Shifted Young tableaux & Hook numbers & Bulgarian Solitaire

I would like to find articles or documentation regarding this process: Starting from what ever integer partition, e.g. 5,2 for the number 7. Construct his Young tableaux and then fill it with Hook ...
5
votes
1answer
274 views

Olympic Badminton, or How to Design a Tournament

Hearing the recent news about disqualified Badminton players in the ongoing 2012 London Olympics got me wondering about how best to design tournaments to avoid situations where players are ...
1
vote
1answer
170 views

Term for a fully connected balanced graph (Rock paper scissor)

Is there a mathematical, graph theory, game theory term for a graph that is fully connected and balanced evenly with each other node. I'm thinking in situations like Rock paper scissors where each ...