Graph details

Graph # 32258

Adjacency matrix

[Too large to display]

Adjacency list

[Too large to display]

HoG graph id

32258

Graph name

Bulgarian Solitaire Tree N=10

Graph submitted by

Kevin Ryde

Invariant values

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

Comments

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.

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