Seminar iz diskretne matematike

Vodji seminarja: Boštjan Brešar in Sandi Klavžar
Predavanja potekajo ob ponedeljkih ob 15:15 v seminarski sobi P1 (Gosposvetska cesta 84, v 4. nadstropju).

Bodoča predavanja

Minula predavanja

Minimal asymmetric graphs

17. 12. 2008

Predavatelj: Gert Sabidussi (McGill University, Montreal and Universite de Montreal)

A classic result of Erdos and Renyi (1963) states that almost
all graphs are asymmetric (i.e. have no non-trivial automorphism).
Given the preponderance of asymmetric graphs, it is tempting to
believe that minimal asymmetric graphs (i.e. those asymmetric graphs
every proper non-trivial induced subgraph of which has a non-trivial
automorphism) are a common occurrence, at least in the crude sense
that there are infinitely many of them. We show that this is not the
case: there are very few (in fact, exactly 18) minimal asymmetric
graphs and they are surprisingly small, having 6, 7 or 8 vertices.
Moreover, it turns out that these graphs are also precisely the mini-
mal graphs that do not have involutory automorphisms. (Joint work
with Jarik Nesetril and Jerome Gagnon.)

Vsi seminarji
Accessibility