Graph details

Graph # 48173

Adjacency matrix

[Too large to display]

Adjacency list

[Too large to display]

HoG graph id


Graph name

(5,5) cage

Graph submitted by

Sancuan Zhang

Invariant values

The definitions of the invariants can be found here.
Invariant Value Invariant Value
Acyclic No Index 5
Algebraic Connectivity 2.764 Laplacian Largest Eigenvalue 8.236
Average Degree 5 Longest Induced Cycle 14
Bipartite No Longest Induced Path 16
Chromatic Index Computation time out Matching Number 15
Chromatic Number 4 Maximum Degree 5
Circumference 30 Minimum Degree 5
Claw-Free No Minimum Dominating Set 7
Clique Number 2 Number of Components 1
Connected Yes Number of Edges 75
Density 0.172 Number of Triangles 0
Diameter 3 Number of Vertices 30
Edge Connectivity 5 Planar No
Eulerian No Radius 3
Genus 9 Regular Yes
Girth 5 Second Largest Eigenvalue 2.236
Hamiltonian Yes Smallest Eigenvalue -3.236
Independence Number 10 Vertex Connectivity 5

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


Posted by Sancuan Zhang at Jan 1, 2022 12:30 PM.
A 5-regular graph with girth 5 has at least 30 vertices; any graph attaining the minimum is called a (5,5) cage.

The graph has 30 automorphisms.

See the paper Exoo, G. , & Jajcay, R. . (2011). Dynamic cage survey. The Electronic Journal of Combinatorics electronic only. Link:

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