Graph details

Graph # 32260

Adjacency matrix

[Too large to display]

Adjacency list

[Too large to display]

HoG graph id


Graph name

Bulgarian Solitaire Tree N=15

Graph submitted by

Kevin Ryde

Invariant values

The definitions of the invariants can be found here.
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.

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