Grafy rozszerzalne - Perl, Monika
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.
Keywords: zbiory doskonale dominujące; zbiory prawie doskonałe; zbiory niezależne; produkty grafów; grafy