Graph details

Graph # 48173

Adjacency matrix

[Too large to display]

Adjacency list

[Too large to display]

HoG graph id

48173

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.

Comments

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:https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS16/pdf

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