Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: induced-hereditary

Sortuj według:

Ogranicz wyniki do:

Universality in Graph Properties with Degree Restrictions

100%

Broere I., Heidema J., Mihók P.

Discussiones Mathematicae Graph Theory

2013

tom 33

nr 3

477-492

Rado constructed a (simple) denumerable graph R with the positive integers as vertex set with the following edges: For given m and n with m < n, m is adjacent to n if n has a 1 in the m’th position of its binary expansion. It is well known that R is a universal graph in the set [...] of all countable graphs (since every graph in [...] is isomorphic to an induced subgraph of R). A brief overview of known universality results for some induced-hereditary subsets of [...] is provided. We then construct a k-degenerate graph which is universal for the induced-hereditary property of finite k-degenerate graphs. In order to attempt the corresponding problem for the property of countable graphs with colouring number at most k + 1, the notion of a property with assignment is introduced and studied. Using this notion, we are able to construct a universal graph in this graph property and investigate its attributes.

Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik

Unique factorization theorem

100%

Mihók P.

Discussiones Mathematicae Graph Theory

2000

tom 20

nr 1

143-154

A property of graphs is any class of graphs closed under isomorphism. A property of graphs is induced-hereditary and additive if it is closed under taking induced subgraphs and disjoint unions of graphs, respectively. Let 𝓟₁,𝓟₂, ...,𝓟ₙ be properties of graphs. A graph G is (𝓟₁,𝓟₂,...,𝓟ₙ)-partitionable (G has property 𝓟₁ º𝓟₂ º... º𝓟ₙ) if the vertex set V(G) of G can be partitioned into n sets V₁,V₂,..., Vₙ such that the subgraph $G[V_i]$ of G induced by V_i belongs to $𝓟_i$; i = 1,2,...,n. A property 𝓡 is said to be reducible if there exist properties 𝓟₁ and 𝓟₂ such that 𝓡 = 𝓟₁ º𝓟₂; otherwise the property 𝓡 is irreducible. We prove that every additive and induced-hereditary property is uniquely factorizable into irreducible factors. Moreover the unique factorization implies the existence of uniquely (𝓟₁,𝓟₂, ...,𝓟ₙ)-partitionable graphs for any irreducible properties 𝓟₁,𝓟₂, ...,𝓟ₙ.

Ograniczanie wyników

2 Discussiones Mathematicae Graph Theory

2 Mihók P.

1 Broere I.

1 Heidema J.

1 2013

1 2000

Wyniki wyszukiwania

Universality in Graph Properties with Degree Restrictions

Unique factorization theorem