Generalizing the graph leads me to suggest a graph minimization problem. For a given alphabet S, a graph G is a "domino graph" for S if the nodes of G can be labeled with letters from S in such a way that every distinct pair of letters occurs as the labels of nodes connected by an edge of G. Clearly the smallest domino graph for an n-letter alphabet is the order-n complete graph. But if we put restrictions on the graph, the problem becomes non-trivial. Michael Beeler asks about rectangular graphs. But what if we only need planarity? For five letters, I can do it with six nodes. For six letters I managed 8 nodes but couldn't prove that 7 was impossible. Thoughts? (As a map coloring problem, this asks for the smallest number of countries in an n-color map so that every color pair occurs on some boundary.) On Tue, Aug 31, 2010 at 1:09 AM, Ed Pegg Jr <ed@mathpuzzle.com> wrote:

Put numbers 1-9 in a 4x7 grid so that all combinations appear as a domino somewhere in the grid.

c corner e edge i interior

1 ccee, 6 eei, 2 iic -- this is a possible distribution solving the 4x7. A careful search proves there are no solutions.

I've found 387 solutions, so far, for the 5x6 grid with holes (0). Here are some of them.

113441 112452 113452 112452 144562 345661 520677 670188 640751 678477 178577 247841 548638 274337 248738 208339 308339 207398 798532 294655 798632 299655 259466 996358 261992 398691 195692 314681 219281 172152

145672 413563 435463 113412 112342 132412 305174 403764 406783 566472 566357 156477 882184 772118 996197 770886 580193 840339 962953 982955 322157 933599 284478 298869 463973 386942 148852 182542 299671 255761

122342 001564 004551 014564 045561 045664 456647 277524 462274 067268 077228 077894 850995 883329 861334 238298 213398 116218 833781 596119 891859 431155 415864 433258 291761 476843 297763 499773 499763 279953

For the 0-9 case without doubles, there is a simpler non-existence proof for the 4x7. An interior square can be surrounded by 4 other numbers. 4+4=8. Each number has to touch 9 other numbers. Each number must therefore be in at least 3 positions of the grid. 30 positions cannot be fit into 28 places.

I wouldn't be surprised if I (that is, my computer) was the first to solve the tightly packed domino problem. This was hard, and required a fairly specialized program. It took awhile for my programs to run.

--Ed Pegg Jr

--- On Sat, 8/28/10, Michael Beeler <mikebeeler@verizon.net> wrote:

From: Michael Beeler <mikebeeler@verizon.net> Subject: [math-fun] domino networks reference sought To: "math-fun" <math-fun@mailman.xmission.com> Date: Saturday, August 28, 2010, 11:28 AM

A month or two ago, someone (Ed Pegg Jr. ?) posed a problem I'm calling "domino network". Surely this isn't new, but I didn't find any mention via some web searches. Anyone know of a reference?

Problem: Label the nodes of a 4x7 rectangular graph with 0 through 9 (repeats allowed), such that each of the 45 edges corresponds to a different domino in the set of 45 dominoes with 0 (blank) through 9 pips, without doubles.

The above problem is impossible (sketch below). I'm looking into related problems: varying the pip limit, whether doubles are included or not, and using various simple shapes on a squre, triangular, or hexagonal grid. Thanks for any comments!

-- Mike Beeler

Proof by contradiction. Suppose there is a solution. Consider the set of nodes labeled "0". Together, they must connect to 9 other nodes: once to a "1", once to a "2", etc. This is true of the nodes with any given label. So, the solution has 10 sets of nodes, each set connecting to exactly 9 other nodes. The given graph has 4 nodes (the corners) with valence 2; 14 nodes (sides) of valence 3; and 10 of valence 4. There is no way to partition these 28 nodes into 10 sets with the valence sum in each set being 9.

I'm calling these "domino networks" because "domino graph" seems to already mean other things. (A particular 6-node graph, per MathWorld; or, a graph with a domino at each node, and links between dominos that have no number of pips in common, per the maa.org page by Ed. There is IBM Lotus Domino, a server product, so "domino network" is unfortunately a bit ambiguous too.)

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

Ed Pegg Jr wrote on 8/31/2010:

Put numbers 1-9 in a 4x7 grid so that all combinations appear as a domino [doubles included] somewhere in the grid.

c corner e edge i interior

1 ccee, 6 eei, 2 iic -- this is a possible distribution solving the 4x7. A careful search proves there are no solutions.

I think that 1 ccci, 7 eei, 1 iic is the only other possible distribution. My program agrees, no solutions with either one.

I've found 387 solutions, so far, for the 5x6 grid with holes (0). Here are some of them. [...]

For the four distinct locations A..D of a single hole, x x x x x x A B x x x C D x x x x x x x x x x x x x x x x x my program finds 108, 50, 81 and 206 solutions respectively. I think the solutions in each class are distinct; if so, that's a grand total of 445 distinct solutions.

For the 0-9 case without doubles, there is a simpler non-existence proof for the 4x7. An interior square can be surrounded by 4 other numbers. 4+4=8. Each number has to touch 9 other numbers. Each number must therefore be in at least 3 positions of the grid. 30 positions cannot be fit into 28 places.

Nice!

I wouldn't be surprised if I (that is, my computer) was the first to solve the tightly packed domino problem. [...]

So maybe these are new results? Great! "Tightly packed" suggests calling these "domino clusters". With caramel and a chocolate covering -- delicious. :-) If we allow holes, I like the 5x6 with two holes. There's only one distinct such pattern, and (my program says) there is a unique (under rotation and label permutation) solution! Allowing holes opens up a huge space of possible patterns. I like to focus on elementary, un-holey shapes. An alternative is Allan Wechsler's generalization to just planarity. Allan says,

(As a map coloring problem, this asks for the smallest number of countries in an n-color map so that every color pair occurs on some boundary.)

Do we also need to specify whether each color occurs paired with itself, like we specify whether domino doubles are included or excluded? SPOILER ALERT: solution to 5x6 with 2 holes 0 1 2 2 3 4 1 5 4 3 6 7 7 4 8 6 8 2 9 8 3 1 6 5 5 7 9 9 3 0 -- Mike