Graph details

Graph # 45613

Adjacency matrix

[Too large to display]

Adjacency list

[Too large to display]

HoG graph id


Graph name


Graph submitted by

Jan Goedgebeur

Invariant values

The definitions of the invariants can be found here.
Invariant Value Invariant Value
Acyclic No Index 9.301
Algebraic Connectivity 7.298 Laplacian Largest Eigenvalue 14.372
Average Degree 9.28 Longest Induced Cycle 6
Bipartite No Longest Induced Path 4
Chromatic Index Computation time out Matching Number 12
Chromatic Number 6 Maximum Degree 10
Circumference 25 Minimum Degree 8
Claw-Free No Minimum Dominating Set 3
Clique Number 3 Number of Components 1
Connected Yes Number of Edges 116
Density 0.387 Number of Triangles 36
Diameter 2 Number of Vertices 25
Edge Connectivity 8 Planar Computation time out
Eulerian No Radius 2
Genus Computation time out Regular No
Girth 3 Second Largest Eigenvalue 1
Hamiltonian Yes Smallest Eigenvalue -5
Independence Number 6 Vertex Connectivity 8

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


Posted by Jan Goedgebeur at May 31, 2021 12:45 PM.
The unique 6-vertex-critical (P6,diamond,K4)-free graph.

Posted by Jan Goedgebeur at Jun 17, 2021 9:20 AM.
See "J. Goedgebeur, Shenwei Huang, Yiao Ju and Owen Merkel, Colouring graphs with no induced six-vertex path or diamond, arXiv preprint: arXiv:2106.08602" for more details.

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