Dowolne podziały grafów

Abstract

The dissertation presents results on arbitrary partitions of a vertex set of a graph G into connected induced subgraphs and on graphs which are arbitrarily decomposable into trails. In the first part we deal with arbitrarily vertex decomposable graphs. We present some families of arbitrarily vertex decomposable trees and unicyclic graphs. We also consider realizations of some specific admissible sequences. In the second part we discuss results on graphs which are arbitrarily decomposable into trails. We solve completely a problem on decomposition of complete bipartite graphs into closed trails that was proposed by E. J. Billington. Next, we prove that bipartite graphs are arbitrarily decomposable into closed directed trails. Also, it is shown that complete graphs, complete bipartite graphs and complete tripartite graphs are arbitrarily decomposable graphs into open and closed trails.

Rozprawa miała na celu przedstawić rezultaty badań dotyczących dowolnego podziału zbioru wierzchołków grafu na części indukujące grafy spójne oraz dowolnych rozkładów grafów na drogi. Część pierwsza dotyczyła wierzchołkowego podziału grafów. Zostały scharakteryzowane pewne rodziny drzew dowolnie podzielnych oraz dowiedziono również dowolnej podzielności pewnych rodzin grafów unicyklicznych. Rozważano także realizacje specyficznych ciągów dopuszczalnych. W drugiej części pracy poruszono tematykę rozkładu grafów na drogi zamknięte. Rozwiązano wpierw problem postawiony przez EJ. Billington, dotyczący rozkładu grafów dwudzielnych na drogi zamknięte. Następnie dowiedziono, że digrafy dwudzielne są dowolnie rozkładalne na skierowane drogi zamknięte. Wykazano również, że grafy pełne, pełne dwudzielne oraz pełne trójdzielne są dowolnie rozkładalne na drogi otwarte i zamknięte.