Graph details

Graph # 33609

Adjacency matrix

[Too large to display]

Adjacency list

[Too large to display]

HoG graph id


Graph name

Binary Tree Rotate A-Empty N=5

Graph submitted by

Kevin Ryde

Invariant values

The definitions of the invariants can be found here.
Invariant Value Invariant Value
Acyclic No Index 3.239
Algebraic Connectivity 0.041 Laplacian Largest Eigenvalue 6.908
Average Degree 2.667 Longest Induced Cycle 4
Bipartite Yes Longest Induced Path 18
Chromatic Index 4 Matching Number 20
Chromatic Number 2 Maximum Degree 4
Circumference 30 Minimum Degree 1
Claw-Free No Minimum Dominating Set 13
Clique Number 2 Number of Components 1
Connected Yes Number of Edges 56
Density 0.065 Number of Triangles 0
Diameter 16 Number of Vertices 42
Edge Connectivity 1 Planar Yes
Eulerian No Radius 8
Genus 0 Regular No
Girth 4 Second Largest Eigenvalue 2.971
Hamiltonian No Smallest Eigenvalue -3.239
Independence Number 22 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 Feb 17, 2019 8:06 AM.
Each vertex represents a binary tree of N=5 vertices (there are Catalan(5)=42 such). Each edge is by a "rotate" where the first subtree of the rotate is empty. (Or equivalently where the end subtree is empty, that being the same by mirror image and rotate other way.) The result is edge intersection of Tamari (rotate) and Stanley (flip) lattices.

A. Bonnin and J.M. Pallo, "A Shortest Path Metric on Unlabelled Binary
Trees", Pattern Recognition Letters, volume 13, 1992, pages 411-415.

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