Graph details

Graph # 45608

Adjacency matrix

000000000100
000000000001
000000000010
000001010100
000000101100
000100100010
000011000001
000100001001
000010010010
100110000000
001001001000
010000110000

Adjacency list

1: 10
2: 12
3: 11
4: 6 8 10
5: 7 9 10
6: 4 7 11
7: 5 6 12
8: 4 9 12
9: 5 8 11
10: 1 4 5
11: 3 6 9
12: 2 7 8

HoG graph id

45608

Graph name

n/a

Graph submitted by

Mikhail Lavrov

Invariant values

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

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

Comments

Posted by Mikhail Lavrov at Apr 20, 2021 4:26 PM.
The smallest counterexample to a conjecture of Gallai; for every vertex in this graph, there is a longest path not containing that vertex. Discovered by Walther and Voss (1974) and independently Zamfirescu (1976); Chen (2018) showed that all such graphs must have matching number at least 6, and therefore this graph has the smallest possible number of vertices.

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