# Graph details

 01110000 10001100 10010010 10100001 01000110 01001001 00101001 00010110

 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

34007

Bicorn

## 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
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.