Premium
On extremal nonsolid bricks
Author(s) -
Feng Xing,
Lu Fuliang
Publication year - 2021
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22648
Subject(s) - combinatorics , mathematics , brick , conjecture , graph , matching (statistics) , statistics , archaeology , history
A 3‐connected graph is a brick if, after the removal of any two distinct vertices, the resulting graph has a perfect matching. Lovász proved that the dimension of the matching lattice of a brick G is equal to| E ( G ) | − | V ( G ) | + 1 . We say a brick G is extremal if the number of perfect matchings in G is exactly d i m ( G ) . de Carvalho et al. characterized extremal bricks and conjectured that every extremal nonsolid brick other than the Petersen graph is the result of the splicing of an extremal brick and aK 4 , up to multiple edges . In this paper, we present an infinite family of graphs showing that this conjecture fails.