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

32260

Bulgarian Solitaire Tree N=15

Kevin Ryde

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

Acyclic | Yes | Index | 2.697 |

Algebraic Connectivity | 0.002 | Laplacian Largest Eigenvalue | 6.246 |

Average Degree | 1.989 | Longest Induced Cycle | undefined |

Bipartite | Yes | Longest Induced Path | 29 |

Chromatic Index | Computation time out | Matching Number | 84 |

Chromatic Number | Computation time out | Maximum Degree | 4 |

Circumference | undefined | Minimum Degree | 1 |

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

Clique Number | 2 | Number of Components | 1 |

Connected | Yes | Number of Edges | 175 |

Density | 0.011 | Number of Triangles | 0 |

Diameter | 29 | Number of Vertices | 176 |

Edge Connectivity | 1 | Planar | Yes |

Eulerian | No | Radius | 15 |

Genus | 0 | Regular | No |

Girth | undefined | Second Largest Eigenvalue | 2.668 |

Hamiltonian | No | Smallest Eigenvalue | -2.697 |

Independence Number | Computation time out | 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:22 AM.

Each vertex is a partition of N=15, ie. a set of integers which sum to 15. There are 176 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=15 is a triangular number and the steps form a tree ending at partition 1+2+3+4+5 which is unchanged by the solitaire rule.

A drawing of this tree can be found in Jerrold R. Griggs and Chih-Chang Ho, "The Cycling of Partitions and Compositions Under Repeated Shifts", Advances In Applied Mathematics, volume 21, 1998, pages 205-227, Am980597, figure 4.

https://core.ac.uk/download/pdf/82612071.pdf

N=15 is a triangular number and the steps form a tree ending at partition 1+2+3+4+5 which is unchanged by the solitaire rule.

A drawing of this tree can be found in Jerrold R. Griggs and Chih-Chang Ho, "The Cycling of Partitions and Compositions Under Repeated Shifts", Advances In Applied Mathematics, volume 21, 1998, pages 205-227, Am980597, figure 4.

https://core.ac.uk/download/pdf/82612071.pdf

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