Graph details

Graph # 33559

Adjacency matrix

[Too large to display]

Adjacency list

[Too large to display]

HoG graph id


Graph name

Kreweras Lattice 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 6.031
Algebraic Connectivity 1.962 Laplacian Largest Eigenvalue 13.027
Average Degree 5.714 Longest Induced Cycle 20
Bipartite Yes Longest Induced Path 20
Chromatic Index 10 Matching Number 20
Chromatic Number 2 Maximum Degree 10
Circumference Computation time out Minimum Degree 4
Claw-Free No Minimum Dominating Set 7
Clique Number 2 Number of Components 1
Connected Yes Number of Edges 120
Density 0.139 Number of Triangles 0
Diameter 4 Number of Vertices 42
Edge Connectivity Computation time out Planar Computation time out
Eulerian No Radius 4
Genus Computation time out Regular No
Girth 4 Second Largest Eigenvalue 3.295
Hamiltonian Computation time out Smallest Eigenvalue -6.031
Independence Number 22 Vertex Connectivity Computation time out

A table row rendered like this indicates that the graph is marked as being interesting for that invariant.


Posted by Kevin Ryde at Feb 9, 2019 8:18 AM.
Each graph vertex is one of the Catalan(5)=42 partitions of the integers 1..5 into non-crossing sets. Such a partition corresponds to an ordered rooted forest (its sets of siblings), and hence to a binary tree too.

Each graph edge is where one set in the partition splits into two to reach another partition (and hence is "graded" by number of sets in the partition).

G. Kreweras, "Sur les Partitions Non-Croisées d'Un Cycle", Discrete
Mathematics, volume 1, number 4, 1971, pages 333-350.

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