Graph details

Adjacency matrix
01110000

10001100

10010010

10100001

01000110

01001001

00101001

00010110


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
34007
Graph name
Bicorn
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

ClawFree

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.
Comments
Posted by Nishad Kothari at Sep 17, 2019 9:18 PM.
A brick is a 3connected 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 Ge is matching covered; furthermore, e is binvariant if the tight cut decomposition of Ge yields precisely one brick.
Lovász conjectured that every brick, distinct from K4, the triangular prism and the Petersen graph, has a binvariant edge.
This conjecture was proved in a series of two papers by Carvalho, Lucchesi and Murty (On a conjecture of Lovász concerning bricks, JCTB 2002).
Carvalho, Lucchesi and Murty proved a stronger statement. In particular, they showed that the Bicorn is the only brick that has a unique binvariant 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, JCTB 2007). Each staircase is devoid of strictly thin edges.
You need to be logged in to be able to add comments.