Direkt zum Inhalt

Lexikon der Mathematik: Kano, Satz von

gibt eine hinreichende Bedingung für die Existenz von fast-regulären Faktoren in einem regulären Multigraphen.

Ein Faktor F eines Multigraphen G, dessen Zusammenhangskomponenten k- oder (k + 1)-regulär sind (k ∈ ℕ0), heißt k-fast-regulär. Durch Anwenden des (g, f)-Faktor-Satzes von L.Lovász (Faktortheorie) präsentierte M.Kano 1986 folgende interessante Ergänzung zum I. Satz von Petersen (Faktortheorie) für den Fall von regulären Multigraphen ungeraden Grades.

Ist G ein r-regulärer Multigraph, so besitzt G einen k-fast-regulären Faktor für alle ganzen Zahlen k mit

0 ≤ k ≤ (2r)/3 − 1.

Darüber hinaus konstruierte Kano r-reguläre Graphen, die für \begin{eqnarray}r-\sqrt{r+1}\lt k\le r-2\end{eqnarray} keinen k-fast-regulären Faktor besitzen. Der Fall \begin{eqnarray}(2r)/3\le k\le r-\sqrt{r+1}\end{eqnarray} ist bis heute noch ungeklärt.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos