Premium
The Average Degree of Minimally Contraction‐Critically 5‐Connected Graphs
Author(s) -
Ando Kiyoshi,
Egawa Yoshimi,
Kriesell Matthias
Publication year - 2014
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.21741
Subject(s) - edge contraction , mathematics , combinatorics , contractible space , contraction (grammar) , graph , discrete mathematics , connectivity , line graph , voltage graph , medicine
Abstract An edge of a 5‐connected graph is said to be 5‐removable (resp. 5‐contractible) if the removal (resp. the contraction) of the edge results in a 5‐connected graph. A 5‐connected graph with neither 5‐removable edges nor 5‐contractible edges is said to be minimally contraction‐critically 5‐connected. We show the average degree of every minimally contraction‐critically 5‐connected graph is less than 15 2 . This bound is sharp in the sense that for any positive real number ε, there is a minimally contraction‐critically 5‐connected graph whose average degree is greater than15 2 − ɛ .