Graph details

Graph # 126

Adjacency matrix

000000000
001100000
010000010
010000001
000001100
000010010
000010001
001001000
000100100

Adjacency list

1:
2: 3 4
3: 2 8
4: 2 9
5: 6 7
6: 5 8
7: 5 9
8: 3 6
9: 4 7

HoG graph id

126

Graph name

n/a

Graph submitted by

GraPHedron

Invariant values

The definitions of the invariants can be found here.
Invariant Value Invariant Value
Acyclic No Index 2
Algebraic Connectivity 0 Laplacian Largest Eigenvalue 4
Average Degree 1.778 Longest Induced Cycle 8
Bipartite Yes Longest Induced Path 6
Chromatic Index 2 Matching Number 4
Chromatic Number 2 Maximum Degree 2
Circumference 8 Minimum Degree 0
Claw-Free Yes Minimum Dominating Set 4
Clique Number 2 Number of Components 2
Connected No Number of Edges 8
Density 0.222 Number of Triangles 0
Diameter infinity Number of Vertices 9
Edge Connectivity 0 Planar Yes
Eulerian No Radius undefined
Genus undefined Regular No
Girth 8 Second Largest Eigenvalue 1.414
Hamiltonian No Smallest Eigenvalue -2
Independence Number 5 Vertex Connectivity 0

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

Comments

Posted by GraPHedron at Mar 28, 2012 11:56 AM.
Is an extremal graph found by GraPHedron. See "H. Melot, Facet defining inequalities among graph invariants: the system graphedron. Discrete Applied Mathematics 156 (2008), 1875-1891" for more information.

Posted by Kevin Ryde at Oct 7, 2017 3:57 AM.
Knight Grid 3x3. Each vertex is a square of a 3x3 chess board. Edges are moves a knight can make. The middle square has no possible moves so is an isolated vertex. Moves among the outer squares make an 8-cycle.

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