Temat: hereditary property of graphs - Katalog OPAC zbiorów

Skocz do pozycji: 1.

Tytuł:: The order of uniquely partitionable graphs
Autorzy:: Broere, Izak
Frick, Marietjie
Mihók, Peter
Powiązania:: https://bibliotekanauki.pl/articles/972025.pdf
Data publikacji:: 1997
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: hereditary property of graphs
uniquely partitionable graphs
Opis:: Let ₁,...,ₙ be properties of graphs. A (₁,...,ₙ)-partition of a graph G is a partition {V₁,...,Vₙ} of V(G) such that, for each i = 1,...,n, the subgraph of G induced by $V_i$ has property $_i$. If a graph G has a unique (₁,...,ₙ)-partition we say it is uniquely (₁,...,ₙ)-partitionable. We establish best lower bounds for the order of uniquely (₁,...,ₙ)-partitionable graphs, for various choices of ₁,...,ₙ.
Źródło:: Discussiones Mathematicae Graph Theory; 1997, 17, 1; 115-125
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 2.

Tytuł:: Maximal graphs with respect to hereditary properties
Autorzy:: Broere, Izak
Frick, Marietjie
Semanišin, Gabriel
Powiązania:: https://bibliotekanauki.pl/articles/972029.pdf
Data publikacji:: 1997
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: hereditary property of graphs
maximal graphs
vertex partition
Opis:: A property of graphs is a non-empty set of graphs. A property P is called hereditary if every subgraph of any graph with property P also has property P. Let P₁, ...,Pₙ be properties of graphs. We say that a graph G has property P₁∘...∘Pₙ if the vertex set of G can be partitioned into n sets V₁, ...,Vₙ such that the subgraph of G induced by V_i has property $P_i$; i = 1,..., n. A hereditary property R is said to be reducible if there exist two hereditary properties P₁ and P₂ such that R = P₁∘P₂. If P is a hereditary property, then a graph G is called P- maximal if G has property P but G+e does not have property P for every e ∈ E([G̅]). We present some general results on maximal graphs and also investigate P-maximal graphs for various specific choices of P, including reducible hereditary properties.
Źródło:: Discussiones Mathematicae Graph Theory; 1997, 17, 1; 51-66
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 3.

Tytuł:: Uniquely partitionable graphs
Autorzy:: Bucko, Jozef
Frick, Marietjie
Mihók, Peter
Vasky, Roman
Powiązania:: https://bibliotekanauki.pl/articles/972032.pdf
Data publikacji:: 1997
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: hereditary property of graphs
additivity
reducibility
vertex partition
Opis:: Let ₁,...,ₙ be properties of graphs. A (₁,...,ₙ)-partition of a graph G is a partition of the vertex set V(G) into subsets V₁, ...,Vₙ such that the subgraph $G[V_i]$ induced by $V_i$ has property $_i$; i = 1,...,n. A graph G is said to be uniquely (₁, ...,ₙ)-partitionable if G has exactly one (₁,...,ₙ)-partition. A property is called hereditary if every subgraph of every graph with property also has property . If every graph that is a disjoint union of two graphs that have property also has property , then we say that is additive. A property is called degenerate if there exists a bipartite graph that does not have property . In this paper, we prove that if ₁,..., ₙ are degenerate, additive, hereditary properties of graphs, then there exists a uniquely (₁,...,ₙ)-partitionable graph.
Źródło:: Discussiones Mathematicae Graph Theory; 1997, 17, 1; 103-113
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 4.

Tytuł:: A survey of hereditary properties of graphs
Autorzy:: Borowiecki, Mieczysław
Broere, Izak
Frick, Marietjie
Mihók, Peter
Semanišin, Gabriel
Powiązania:: https://bibliotekanauki.pl/articles/971986.pdf
Data publikacji:: 1997
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: hereditary property of graphs
vertex partition
reducible property
graph invariants
complexity
Opis:: In this paper we survey results and open problems on the structure of additive and hereditary properties of graphs. The important role of vertex partition problems, in particular the existence of uniquely partitionable graphs and reducible properties of graphs in this structure is emphasized. Many related topics, including questions on the complexity of related problems, are investigated.
Źródło:: Discussiones Mathematicae Graph Theory; 1997, 17, 1; 5-50
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Informacja