Related Links (Outside this Site)

---

(2007-03-19)   Brocoum's Poser Generalized
Markings of one edge per node in which no edge is marked twice.

There are  d  ways to mark only one edge at a node of degree d.  The total number of unrestricted markings is simply the product of the degrees of all nodes.  Among those, we want to enumerate the markings for which no edge is marked twice  (once for each of the two nodes it connects).

Philip Brocoum posed a special case of this problem (2007-03-10; e-mail) after pondering it for more than a year (2006-01-26).

One lesser generalization of Brocoum's poser is to consider  married people in a circle where no two spouses are neighbors, with the rule that one person may only look at a neighbor or a spouse  (Brocoum's original puzzle considered a circle of 10 people, with spouses always sitting at opposite locations across the circle).  We want to enumerate the scenarios where nobody makes eye contact.

In technical terms, this is a restriction of our general problem to undirected cubic Hamiltonian graphs  (namely, graphs where 3 edges meet at each node and which allow a circuit that goes through every node once and only once).

With 4 nodes, there's only one such graph  (the regular tetrahedron)  in which there are 30 different satisfactory markings  (out of 81 unrestricted possibilities). 

With 6 nodes, Hamiltonian cubic graphs have 729 possible markings (3⁶ ).  Two configurations lead to different numbers of satisfactory markings  (156 or 158).

With 8 nodes, the number of satisfactory markings is  826, 828, 834, 842 or 860.

Note that the leftmost of the above graphs is isomorphic to the Brocoum case  (where two spouses are always in diametrically opposed positions).  To prove this, you may want to look for a Hamiltonian circuit besides the "obvious" outer circle and redraw the graph accordingly.  (Numbering the nodes helps!).

Incidentally, the well-known NP-completeness of determining  graph isomorphism  implies the truth of at least one of the following statements concerning the tally of the satisfactory markings of a general graph:

• Two non-isomorphic [cubic] graphs may yield the same tally.
• Computing the tally of a [cubic] graph is an NP-complete problem.

For Hamiltonian cubic graphs with 10 nodes, the tallies of satisfactory markings can have one of 16 different values:  4384, 4392, 4406, 4408, 4416, 4438, 4446, 4456, 4476, 4484, 4494, 4502, 4530, 4556, 4600 or 4602.

Similarily, there are 75 classes of Hamiltonian cubic graphs with 12 nodes  (one such class is illustrated by the hexagonal prism at right)  which yield the following 75 tallies:
23248, 23256, 23294, 23310, 23348, 23356, 23358, 23372, 23376, 23404, 23412, 23436, 23450, 23466, 23468, 23522, 23562, 23564, 23592, 23608, 23616, 23626, 23644, 23654, 23662, 23710, 23718, 23726, 23734, 23772, 23788, 23816, 23842, 23868, 23878, 23904, 23922, 23930, 23950, 23968, 23972, 23976, 23984, 23992, 23994, 24022, 24032, 24038, 24076, 24078, 24094, 24108, 24130, 24144, 24164, 24190, 24222, 24226, 24236, 24272, 24274, 24318, 24356, 24380, 24382, 24470, 24516, 24578, 24588, 24598, 24628, 24632, 24640, 24848, 25200.

For any even number of nodes, one example of a Hamiltonian cubic graph is a polygonal prism:  A trivial Hamiltonian circuit is obtained from a clockwise circuit of the top polygon and a counterclockwise circuit of the bottom polygon by replacing the two horizontal edges of one face with the two vertical edges of that particular face.

Here are other pretty representations of some Hamiltonian cubic graphs:

n = 4	n = 6	n = 8

n = 12	n = 20

n = 24