Minimal graphs containing k perfect matchings (Seminar DM)

Iz MaFiRaWiki

Minimal graphs containing k perfect matchings

Gašper Fijavž

Torek, 8. marca 2016, od 10h do 12h, Plemljev seminar, Jadranska 19


Povzetek:

Povzetek: A finite undirected graph is minimally k-matchable, if it has at least k perfect matchings but deleting any edge results in a graph which has not. We prove that, given k, there exists a finite set of graphs Σk, so that every minimally k-matchable graph is an odd subdivision of a graph from Σk.

Seminar za diskretno matematiko

Osebna orodja