Graph details

Graph # 33607

Adjacency matrix

00000000000001
00000000100000
00000001000000
00000000011000
00000100000010
00001000000100
00000000100100
00100000001000
01000010000000
00010000000011
00010001000001
00000110000010
00001000010100
10000000011000

Adjacency list

1: 14
2: 9
3: 8
4: 10 11
5: 6 13
6: 5 12
7: 9 12
8: 3 11
9: 2 7
10: 4 13 14
11: 4 8 14
12: 6 7 13
13: 5 10 12
14: 1 10 11

HoG graph id

33607

Graph name

Binary Tree Rotate A-Empty N=4

Graph submitted by

Kevin Ryde

Invariant values

The definitions of the invariants can be found here.
Invariant Value Invariant Value
Acyclic No Index 2.492
Algebraic Connectivity 0.107 Laplacian Largest Eigenvalue 5.254
Average Degree 2.143 Longest Induced Cycle 4
Bipartite Yes Longest Induced Path 9
Chromatic Index 3 Matching Number 7
Chromatic Number 2 Maximum Degree 3
Circumference 4 Minimum Degree 1
Claw-Free No Minimum Dominating Set 5
Clique Number 2 Number of Components 1
Connected Yes Number of Edges 15
Density 0.165 Number of Triangles 0
Diameter 9 Number of Vertices 14
Edge Connectivity 1 Planar Yes
Eulerian No Radius 5
Genus 0 Regular No
Girth 4 Second Largest Eigenvalue 2.107
Hamiltonian No Smallest Eigenvalue -2.492
Independence Number 7 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 Feb 17, 2019 8:04 AM.
Each vertex represents a binary tree of N=4 vertices (there are Catalan(4)=14 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.