Graph details

Graph # 33557

Adjacency matrix

00001100000010
00000000101001
00000000010101
00000011000010
10000000110001
10000000001101
00010000100101
00010000011001
01001010000010
00101001000010
01000101000010
00100110000010
10010000111100
01101111000000

Adjacency list

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

HoG graph id

33557

Graph name

Kreweras Lattice 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 4.156
Algebraic Connectivity 2 Laplacian Largest Eigenvalue 8.702
Average Degree 4 Longest Induced Cycle 8
Bipartite Yes Longest Induced Path 6
Chromatic Index 6 Matching Number 7
Chromatic Number 2 Maximum Degree 6
Circumference 14 Minimum Degree 3
Claw-Free No Minimum Dominating Set 2
Clique Number 2 Number of Components 1
Connected Yes Number of Edges 28
Density 0.308 Number of Triangles 0
Diameter 3 Number of Vertices 14
Edge Connectivity 3 Planar No
Eulerian No Radius 3
Genus 2 Regular No
Girth 4 Second Largest Eigenvalue 1.525
Hamiltonian Yes Smallest Eigenvalue -4.156
Independence Number 7 Vertex Connectivity 3

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 9, 2019 8:14 AM.
Each graph vertex is one of the Catalan(4)=14 partitions of the integers 1..4 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.