Minimum Degree and Graph Minors

Gašper Fijavž, David R. Wood

Research output: Contribution to journalArticleResearchpeer-review

1 Citation (Scopus)

Abstract

A graph G is a minor minimal minimum degree graph (MMMD) if δ (H) < δ (G) for every proper minor H of G. We (i) determine all complete multipartite MMMD graphs and show that (ii) every small k-regular graph is a MMMD graph. Intuitively it seems that MMMD graphs are highly connected. Countering that (iii) we show that MMMD graphs may have a rich block-structure.

Original languageEnglish
Pages (from-to)79-83
Number of pages5
JournalElectronic Notes in Discrete Mathematics
Volume31
Issue numberC
DOIs
Publication statusPublished - 20 Aug 2008
Externally publishedYes

Keywords

  • forbidden minors
  • graph minors
  • minimum degree

Cite this