Minimal bricks have many vertices of small degree

DOI10.1016/J.EJC.2013.06.045MaRDI QIDQ2441634zbMATH OpenOpenAlexFDO

Authors Henning Bruhn, Maya Stein

Publication date 25 March 2014

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1210.4180

zbMATH Keywords

perfect matching

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We prove that every minimal brick on n vertices has at least n/9 vertices of degree at most 4.

Cites work

• Brick decompositions and the matching rank of graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Generating bricks
• How to build a brick
• scientific article; zbMATH DE number 13859 (Why is no real title available?)
• Matching structure and the matching lattice
• Matching theory
• Minimal bricks

Cited in

(6)

• Minimally k-factor-critical graphs for some large k
• The cubic vertices of solid minimal bricks
• Minimum degree of minimal (n-10)-factor-critical graphs
• On a Norine-Thomas conjecture concerning minimal bricks
• K₄-free planar minimal bricks with the maximum number of edges
• Minimal bricks with the maximum number of edges

This page was built for publication: Minimal bricks have many vertices of small degree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2441634)