Graph details

Graph # 34007

Adjacency matrix


Adjacency list

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

HoG graph id


Graph name


Graph submitted by

Nishad Kothari

Invariant values

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

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


Posted by Nishad Kothari at Sep 17, 2019 9:18 PM.
A brick is a 3-connected graph with the additional property that deleting any two distinct vertices results in a graph that has a perfect matching.

An edge e of a brick G is removable if G-e is matching covered; furthermore, e is b-invariant if the tight cut decomposition of G-e yields precisely one brick.

Lovász conjectured that every brick, distinct from K4, the triangular prism and the Petersen graph, has a b-invariant edge.

This conjecture was proved in a series of two papers by Carvalho, Lucchesi and Murty (On a conjecture of Lovász concerning bricks, JCT-B 2002).

Carvalho, Lucchesi and Murty proved a stronger statement. In particular, they showed that the Bicorn is the only brick that has a unique b-invariant edge.

Posted by Nishad Kothari at Sep 17, 2019 9:25 PM.
The Bicorn, and a related graph called the Tricorn, play important roles in several works of Carvalho, Kothari, Lucchesi and Murty --- two of these are listed below.

1. $K_4$-free and $\overline{C_6}$-free planar matching covered graphs (Kothari and Murty, JGT 2016)

2. On two unsolved problems concerning matching covered graphs (Lucchesi, Carvalho, Kothari and Murty, SIDMA 2018)

Posted by Nishad Kothari at Sep 17, 2019 9:31 PM.
The Bicorn is a member of an infinite family of bricks called Staircases --- these play an important role in the Brick Generation Theorem proved by Norine and Thomas (Generating Bricks, JCT-B 2007). Each staircase is devoid of strictly thin edges.

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