Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 2

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last

Wyniki wyszukiwania

help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Minimal forbidden subgraphs of reducible graph properties

100%
Berger A.
Discussiones Mathematicae Graph Theory
|
2001
|
tom 21
|
nr 1
111-117
EN
A property of graphs is any class of graphs closed under isomorphism. Let 𝓟₁,𝓟₂,...,𝓟ₙ be properties of graphs. A graph G is (𝓟₁,𝓟₂,...,𝓟ₙ)-partitionable if the vertex set V(G) can be partitioned into n sets, {V₁,V₂,..., Vₙ}, such that for each i = 1,2,...,n, the graph $G[V_i] ∈ 𝓟_i$. We write 𝓟₁∘𝓟₂∘...∘𝓟ₙ for the property of all graphs which have a (𝓟₁,𝓟₂,...,𝓟ₙ)-partition. An additive induced-hereditary property 𝓡 is called reducible if there exist additive induced-hereditary properties 𝓟₁ and 𝓟₂ such that 𝓡 = 𝓟₁∘𝓟₂. Otherwise 𝓡 is called irreducible. An additive induced-hereditary property 𝓟 can be defined by its minimal forbidden induced subgraphs: those graphs which are not in 𝓟 but which satisfy that every proper induced subgraph is in 𝓟. We show that every reducible additive induced-hereditary property has infinitely many minimal forbidden induced subgraphs. This result is also seen to be true for reducible additive hereditary properties.
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Prime ideals in the lattice of additive induced-hereditary graph properties

63%
Berger A., Mihók P.
Discussiones Mathematicae Graph Theory
|
2003
|
tom 23
|
nr 1
117-127
EN
An additive induced-hereditary property of graphs is any class of finite simple graphs which is closed under isomorphisms, disjoint unions and induced subgraphs. The set of all additive induced-hereditary properties of graphs, partially ordered by set inclusion, forms a completely distributive lattice. We introduce the notion of the join-decomposability number of a property and then we prove that the prime ideals of the lattice of all additive induced-hereditary properties are divided into two groups, determined either by a set of excluded join-irreducible properties or determined by a set of excluded properties with infinite join-decomposability number. We provide non-trivial examples of each type.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.