Autor:

Perl, Monika

Tytuł:

Grafy rozszerzalne

Temat i słowa kluczowe:

zbiory doskonale dominujące ; zbiory prawie doskonałe ; zbiory niezależne ; produkty grafów ; grafy

Streszczenie:

Treść pracy stanowią rozważania w grafach, w których dowolny k-wierzchołkowy albo k-krawędziowy podzbiór o zadanej własności można rozszerzyć do największego zbioru posiadającego tę własność. Dotyczą one pięciu rodzajów rozszerzalności grafów. Trzy z nich: rozszerzalność rozumiana w sensie Plummera, rozszerzalność w sensie Berge'a w odniesieniu do podzbiorów niezależnych wierzchołków, oraz w odniesieniu do podzbiorów niezależnych krawędzi, są znane w literaturze. Czwarty i piąty rodzaj rozszerzalności zostały zdefiniowane w tej pracy i stanowią próbę przeniesienia problemu rozszerzalności ze zbiorów niezależnych wierzchołków grafu na zbiory prawie doskonałe i doskonale dominujące grafów. Wszystkie rodzaje rozszerzalności grafów badane są ze względu na wysokość stopnia k-rozszerzalności grafu. Najwyższy stopień rozszerzalności grafu zwany liczbą rozszerzalności (dla podzbiorów wierzchołków) albo indeksem rozszerzalności (dla podzbiorów krawędzi) jest wyznaczony lub szacowany dla różnych klas grafów oraz dla produktów grafów. Innym rodzajem problematyki rozważanej wpracy są związki między stopniami rozszerzalności róznych typów, oraz między stopniami rozszerzalności w obrębie tego samego typu.

Abstract:

This PhD thesis is concerned with graphs, whose any subset consisting of k vertices or k edges with given property can be extended to maximum set having this property. Five kinds of extendability are considered. Three of them: extendability understood in the sense of Plummer, extendability in the sense of Berge with respect to independent sets of vertices, and with respect to independent sets of edges, are known in the literature. Fourth and fifth kind of extendability is defined in this thesis and its make an attempt to transpose the problem of extendabilityfrom independent sets of vertices in a graph to nearly perfect sets and perfect dominating sets in graphs. All of those kinds of extendability are studied with respect to size of k-extendability of a graph. The maximum size of extendability of a graph, named the extendability number (for subsets of vertices) or the extendability index (for subsets of edges), is determined or bounded for some classes of graphs and for products of graphs. Another kind of problem, which is considered in this thesis, are relations between parameters of extendability of different types, and between parameters of extendability of the same type.

Opis:

promotor: dr hab. Maria Kwaśnik, Politechnika Rzeszowska, Wydział Matematyki i Fizyki Stosowanej, Katedra Matematyki ; recenzenci: prof. dr hab. Mieczysław Borowiecki, Uniwersytet Zielonogórski, Wydział Matematyki, Informatyki i Ekonometrii<br>prof. dr hab. Maciej M. Sysło, Uniwersytet Wrocławski, Instytut Informatyki ; Uniwersytet Zielonogórski

Data wydania:

2008

Typ zasobu:

rozprawa doktorska

Format:

text/html

Jezyk:

pol

Prawa do dysponowania publikacją:

Biblioteka Uniwersytetu Zielonogórskiego