Mariusz MESZKA

(WMS, AGH)

1-faktoryzacje bez cykli zadanej długości

Mówimy, że 1-faktoryzacja regularnego grafu $G$ jest jednolita jeśli unia dowolnych dwóch 1-faktorów jest izomorficzna z tym samym 2-faktorem $H$, będącym unią rozłącznych wierzchołkowo cykli parzystej długości.

Dotychczas znanych jest zaledwie kilka nieskończonych klas jednolitych 1-faktoryzacji grafów pełnych.

Poprzez kontrast do jednolitych 1-faktoryzacji interesujące wydaje się pytanie o istnienie takich 1-faktoryzacji, w których unia dowolnych dwóch 1-faktorów nie zawiera cykli zadanej długości.

Przedstawione zostaną wyniki dotyczące istnienia takich 1-faktoryzacji grafu pełnego $K_{2n}$, dla których zabroniona jest zadana parzysta długość $k\neq 2n$. Ponadto omówione zostaną pewne rodziny 1-faktoryzacji o zabronionych długościach nie większych niż k.

Serdecznie zapraszamy wszystkich chętnych !