Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

English (EN)·Polski (PL)·Yкраїнський (UK)
Przejdź do strony domowej biblioteki Centralna Biblioteka Wojskowa Link otwiera się w nowym oknie Logo biblioteki Prolib Integro - strona głównaCentralna Biblioteka Wojskowa

Wyszukujesz frazę "hereditary property of graphs" wg kryterium: Temat

  Lista filtrów
Wyrównaj
Wyświetlanie 1-15 z 21
Tytuł:
Reducible properties of graphs
Autorzy:
Mihók, P.
Semanišin, G.
Powiązania:
https://bibliotekanauki.pl/articles/972021.pdf
Data publikacji:
1995
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
hereditary property of graphs
additivity
reducibility
Opis:
Let L be the set of all hereditary and additive properties of graphs. For P₁, P₂ ∈ L, the reducible property R = P₁∘P₂ is defined as follows: G ∈ R if and only if there is a partition V(G) = V₁∪ V₂ of the vertex set of G such that $⟨V₁⟩_G ∈ P₁$ and $⟨V₂⟩_G ∈ P₂$. The aim of this paper is to investigate the structure of the reducible properties of graphs with emphasis on the uniqueness of the decomposition of a reducible property into irreducible ones.
Źródło:
Discussiones Mathematicae Graph Theory; 1995, 15, 1; 11-18
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
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ł
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ł
Tytuł:
Graphs maximal with respect to hom-properties
Autorzy:
Kratochvíl, Jan
Mihók, Peter
Semanišin, Gabriel
Powiązania:
https://bibliotekanauki.pl/articles/971980.pdf
Data publikacji:
1997
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
hom-property of graphs
hereditary property of graphs
maximal graphs
Opis:
For a simple graph H, →H denotes the class of all graphs that admit homomorphisms to H (such classes of graphs are called hom-properties). We investigate hom-properties from the point of view of the lattice of hereditary properties. In particular, we are interested in characterization of maximal graphs belonging to →H. We also provide a description of graphs maximal with respect to reducible hom-properties and determine the maximum number of edges of graphs belonging to →H.
Źródło:
Discussiones Mathematicae Graph Theory; 1997, 17, 1; 77-88
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On the factorization of reducible properties of graphs into irreducible factors
Autorzy:
Mihók, P.
Vasky, R.
Powiązania:
https://bibliotekanauki.pl/articles/972030.pdf
Data publikacji:
1995
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
hereditary property of graphs
additivity
reducibility
vertex partition
Opis:
A hereditary property R of graphs is said to be reducible if there exist hereditary properties P₁,P₂ such that G ∈ R if and only if the set of vertices of G can be partitioned into V(G) = V₁∪V₂ so that ⟨V₁⟩ ∈ P₁ and ⟨V₂⟩ ∈ P₂. The problem of the factorization of reducible properties into irreducible factors is investigated.
Źródło:
Discussiones Mathematicae Graph Theory; 1995, 15, 2; 195-203
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
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ł
Tytuł:
-bipartitions of minor hereditary properties
Autorzy:
Borowiecki, Piotr
Ivančo, Jaroslav
Powiązania:
https://bibliotekanauki.pl/articles/971979.pdf
Data publikacji:
1997
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
minor hereditary property of graphs
generalized colouring
bipartitions of graphs
Opis:
We prove that for any two minor hereditary properties ₁ and ₂, such that ₂ covers ₁, and for any graph G ∈ ₂ there is a ₁-bipartition of G. Some remarks on minimal reducible bounds are also included.
Źródło:
Discussiones Mathematicae Graph Theory; 1997, 17, 1; 89-93
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On generalized list colourings of graphs
Autorzy:
Borowiecki, Mieczysław
Broere, Izak
Mihók, Peter
Powiązania:
https://bibliotekanauki.pl/articles/972024.pdf
Data publikacji:
1997
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
hereditary property of graphs
list colouring
vertex partition number
Opis:
Vizing [15] and Erdős et al. [8] independently introduce the idea of considering list-colouring and k-choosability. In the both papers the choosability version of Brooks' theorem [4] was proved but the choosability version of Gallai's theorem [9] was proved independently by Thomassen [14] and by Kostochka et al. [11]. In [3] some extensions of these two basic theorems to (,k)-choosability have been proved.
In this paper we prove some extensions of the well-known bounds for the -chromatic number to the (,k)-choice number and then an extension of Brooks' theorem.
Źródło:
Discussiones Mathematicae Graph Theory; 1997, 17, 1; 127-132
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Generalized list colourings of graphs
Autorzy:
Borowiecki, Mieczysław
Drgas-Burchardt, Ewa
Mihók, Peter
Powiązania:
https://bibliotekanauki.pl/articles/972045.pdf
Data publikacji:
1995
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
hereditary property of graphs
list colouring
vertex partition number
Opis:
We prove: (1) that $ch_P(G) - χ_P(G)$ can be arbitrarily large, where $ch_P(G)$ and $χ_P(G)$ are P-choice and P-chromatic numbers, respectively, (2) the (P,L)-colouring version of Brooks' and Gallai's theorems.
Źródło:
Discussiones Mathematicae Graph Theory; 1995, 15, 2; 185-193
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Generalized domination, independence and irredudance in graphs
Autorzy:
Borowiecki, Mieczysław
Michalak, Danuta
Sidorowicz, Elżbieta
Powiązania:
https://bibliotekanauki.pl/articles/971966.pdf
Data publikacji:
1997
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
hereditary property of graphs
generalized domination
independence and irredundance numbers
Opis:
The purpose of this paper is to present some basic properties of -dominating, -independent, and -irredundant sets in graphs which generalize well-known properties of dominating, independent and irredundant sets, respectively.
Źródło:
Discussiones Mathematicae Graph Theory; 1997, 17, 1; 147-153
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
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ł
Tytuł:
Gallais innequality for critical graphs of reducible hereditary properties
Autorzy:
Mihók, Peter
Skrekovski, Riste
Powiązania:
https://bibliotekanauki.pl/articles/743466.pdf
Data publikacji:
2001
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
additive induced-hereditary property of graphs
reducible property of graphs
critical graph
Gallai's Theorem
Opis:
In this paper Gallai's inequality on the number of edges in critical graphs is generalized for reducible additive induced-hereditary properties of graphs in the following way. Let $₁,₂,...,ₖ$ (k ≥ 2) be additive induced-hereditary properties, $ = ₁ ∘ ₂ ∘ ... ∘ₖ$ and $δ = ∑_{i=1}^k δ(_i)$. Suppose that G is an -critical graph with n vertices and m edges. Then 2m ≥ δn + (δ-2)/(δ²+2δ-2)*n + (2δ)/(δ²+2δ-2) unless = ² or $G = K_{δ+1}$. The generalization of Gallai's inequality for -choice critical graphs is also presented.
Źródło:
Discussiones Mathematicae Graph Theory; 2001, 21, 2; 167-177
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Note on partitions of planar graphs
Autorzy:
Broere, Izak
Wilson, Bonita
Bucko, Jozef
Powiązania:
https://bibliotekanauki.pl/articles/744336.pdf
Data publikacji:
2005
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
planar graph
hereditary property of graphs
forest and triangle-free graph
Opis:
Chartrand and Kronk in 1969 showed that there are planar graphs whose vertices cannot be partitioned into two parts inducing acyclic subgraphs. In this note we show that the same is true even in the case when one of the partition classes is required to be triangle-free only.
Źródło:
Discussiones Mathematicae Graph Theory; 2005, 25, 1-2; 211-215
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On generating sets of induced-hereditary properties
Autorzy:
Semanišin, Gabriel
Powiązania:
https://bibliotekanauki.pl/articles/743561.pdf
Data publikacji:
2002
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
induced-hereditary property of graphs
additivity
reducibility
generating sets
maximal graphs
unique factorization
Opis:
A natural generalization of the fundamental graph vertex-colouring problem leads to the class of problems known as generalized or improper colourings. These problems can be very well described in the language of reducible (induced) hereditary properties of graphs. It turned out that a very useful tool for the unique determination of these properties are generating sets. In this paper we focus on the structure of specific generating sets which provide the base for the proof of The Unique Factorization Theorem for induced-hereditary properties of graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2002, 22, 1; 183-192
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
The decomposability of additive hereditary properties of graphs
Autorzy:
Broere, Izak
Dorfling, Michael
Powiązania:
https://bibliotekanauki.pl/articles/743814.pdf
Data publikacji:
2000
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
property of graphs
additive
hereditary
decomposable property of graphs
Opis:
An additive hereditary property of graphs is a class of simple graphs which is closed under unions, subgraphs and isomorphisms. If ₁,...,ₙ are properties of graphs, then a (₁,...,ₙ)-decomposition of a graph G is a partition E₁,...,Eₙ of E(G) such that $G[E_i]$, the subgraph of G induced by $E_i$, is in $_i$, for i = 1,...,n. We define ₁ ⊕...⊕ ₙ as the property {G ∈ : G has a (₁,...,ₙ)-decomposition}. A property is said to be decomposable if there exist non-trivial hereditary properties ₁ and ₂ such that = ₁⊕ ₂. We study the decomposability of the well-known properties of graphs ₖ, ₖ, ₖ, ₖ, ₖ, ₖ and $ ^{p}$.
Źródło:
Discussiones Mathematicae Graph Theory; 2000, 20, 2; 281-291
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Wyświetlanie 1-15 z 21

Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies