Graph details

Graph # 896

Adjacency matrix


Adjacency list

3: 4
4: 3
5: 6
6: 5

HoG graph id


Graph name


Graph submitted by


Invariant values

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

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


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 Dec 15, 2018 6:24 AM.
This forest requires at least 3 generators for its automorphism group. Its n=6 vertices is the fewest where a forest requires 3 generators, and this forest is the only such n=6. The automorphism group is (S2 wr S2) x S2, of order 16. S2wrS2 is the dihedral group D4 order 8.

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