## Adjacency matrix[Too large to display] |
## Adjacency list[Too large to display] |

32258

Bulgarian Solitaire Tree N=10

Kevin Ryde

Invariant | Value | Invariant | Value |
---|---|---|---|

Acyclic | Yes | Index | 2.435 |

Algebraic Connectivity | 0.015 | Laplacian Largest Eigenvalue | 5.579 |

Average Degree | 1.952 | Longest Induced Cycle | undefined |

Bipartite | Yes | Longest Induced Path | 17 |

Chromatic Index | 4 | Matching Number | 19 |

Chromatic Number | 2 | Maximum Degree | 4 |

Circumference | undefined | Minimum Degree | 1 |

Claw-Free | No | Minimum Dominating Set | 17 |

Clique Number | 2 | Number of Components | 1 |

Connected | Yes | Number of Edges | 41 |

Density | 0.048 | Number of Triangles | 0 |

Diameter | 17 | Number of Vertices | 42 |

Edge Connectivity | 1 | Planar | Yes |

Eulerian | No | Radius | 9 |

Genus | 0 | Regular | No |

Girth | undefined | Second Largest Eigenvalue | 2.321 |

Hamiltonian | No | Smallest Eigenvalue | -2.435 |

Independence Number | 23 | Vertex Connectivity | 1 |

A table row rendered like this
indicates that the graph is marked as being *interesting* for that invariant.

Posted by Kevin Ryde at Nov 29, 2018 8:09 AM.

Each vertex is a partition of N=10, ie. a set of integers which sum to 10. There are 42 such. Each edge is from a partition to its successor under the Bulgarian solitaire rule: subtract 1 from each element, sum those 1s as a new term, discard any zeros.

N=10 is a triangular number and the steps form a tree ending at partition 1+2+3+4 which is unchanged by the solitaire rule and can be reckoned the tree root. This is the leaf with degree-4 neighbour.

N=10 is the smallest triangular N where the tree has rooted automorphisms. The automorphism group is S2 x S2, being 2 places where can swap subtrees (path-2s at both places). There are no extra automorphisms when treated as a free tree, though this is not first triangular N where free tree automorphisms occur (that is N=3 which is a path-3 down).

Drawn in Martin Gardner, "Mathematical Games: Tasks You Cannot Help Finishing No Matter How Hard You Try to Block Finishing Them", Scientific American, August 1983, pages 12-23.

N=10 is a triangular number and the steps form a tree ending at partition 1+2+3+4 which is unchanged by the solitaire rule and can be reckoned the tree root. This is the leaf with degree-4 neighbour.

N=10 is the smallest triangular N where the tree has rooted automorphisms. The automorphism group is S2 x S2, being 2 places where can swap subtrees (path-2s at both places). There are no extra automorphisms when treated as a free tree, though this is not first triangular N where free tree automorphisms occur (that is N=3 which is a path-3 down).

Drawn in Martin Gardner, "Mathematical Games: Tasks You Cannot Help Finishing No Matter How Hard You Try to Block Finishing Them", Scientific American, August 1983, pages 12-23.

You need to be logged in to be able to add comments.