Zdzisław SKUPIEŃ

(WMS, AGH)

Multikompozycje liczbowe dla zliczania grafów (np. snarków)

Kompozycją liczby n o składnikach z danego zbioru liczb naturalnych $A$ jest ciąg z $A^*$ o sumie wyrazów równej n. Załóżmy, że $A$ jest zbiorem rzędów danych grafów, przy czym dla $y\in A$ symbol $m_y$ oznacza liczbę różnych grafów rzędu y. Kompozycją danych grafów jest graf G otrzymany z ciągu kopii danych grafów przez jakieś połączenie krawędziami sąsiednich kopii. Wtedy liczba grafów G rzędu n (z wyrónionym wierzchołkiem "początkowym" w G) może być liczbą odpowiadających multikompozycji liczby n, w których każdy składnik y ma krotność $m_y$. Snarki otrzymujemy łącząc ze sobą skrajne kopie w rozważanych kompozycjach grafowych typu G. Dla zliczenia klas izomorfizmu takich snarków stosujemy lemat Burnside'a.

Serdecznie zapraszamy wszystkich chętnych!