Naslov
Counting perfect matchings in n-extendable graphs

Autori
Došlić, Tomislav

Izvornik
Discrete Mathematics (0012-365X) 308 (2008); 2297-2300

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

Ključne riječi
n-extendable graph; Perfect matching; Enumeration

Sažetak
The structural theory of matchings is used to establish lower bounds on the number of perfect matchings in n-extendable graphs. It is shown that any such graph on p vertices and q edges contains at least (n + 1)!/4[q − p − (n − 1)(2 Delta − 3) + 4] different perfect matchings, where Delta is the maximum degree of a vertex in G.

Izvorni jezik
Engleski

Znanstvena područja
Matematika

POVEZANOST RADA