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: 10

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

On some variations of extremal graph problems

100%
Semanišin G.
Discussiones Mathematicae Graph Theory
|
1997
|
tom 17
|
nr 1
67-76
EN
A set P of graphs is termed hereditary property if and only if it contains all subgraphs of any graph G belonging to P. A graph is said to be maximal with respect to a hereditary property P (shortly P-maximal) whenever it belongs to P and none of its proper supergraphs of the same order has the property P. A graph is P-extremal if it has a the maximum number of edges among all P-maximal graphs of given order. The number of its edges is denoted by ex(n, P). If the number of edges of a P-maximal graph is minimum, then the graph is called P-saturated and its number of edges is denoted by sat(n, P). In this paper, we consider two famous problems of extremal graph theory. We shall translate them into the language of P-maximal graphs and utilize the properties of the lattice of all hereditary properties in order to establish some general bounds and particular results. Particularly, we shall investigate the behaviour of sat(n,P) and ex(n,P) in some interesting intervals of the mentioned lattice.
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On generating sets of induced-hereditary properties

100%
Semanišin G.
Discussiones Mathematicae Graph Theory
|
2002
|
tom 22
|
nr 1
183-192
EN
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.
3
Content available remote

Maximum Semi-Matching Problem in Bipartite Graphs

64%
Katrenič J., Semanišin G.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 3
559-569
EN
An (f, g)-semi-matching in a bipartite graph G = (U ∪ V,E) is a set of edges M ⊆ E such that each vertex u ∈ U is incident with at most f(u) edges of M, and each vertex v ∈ V is incident with at most g(v) edges of M. In this paper we give an algorithm that for a graph with n vertices and m edges, n ≤ m, constructs a maximum (f, g)-semi-matching in running time O(m ⋅ min [...] ) Using the reduction of [5] our result on maximum (f, g)-semi-matching problem directly implies an algorithm for the optimal semi-matching problem with running time O( [...] log n).
4
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Unique factorization theorem for object-systems

64%
Mihók P., Semanišin G.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 3
559-575
EN
The concept of an object-system is a common generalization of simple graph, digraph and hypergraph. In the theory of generalised colourings of graphs, the Unique Factorization Theorem (UFT) for additive induced-hereditary properties of graphs provides an analogy of the well-known Fundamental Theorem of Arithmetics. The purpose of this paper is to present UFT for object-systems. This result generalises known UFT for additive induced-hereditary and hereditary properties of graphs and digraphs. Formal Concept Analysis is applied in the proof.
5
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Generalized ramsey theory and decomposable properties of graphs

51%
Burr S., Jacobson M., Mihók P., Semanišin G.
Discussiones Mathematicae Graph Theory
|
1999
|
tom 19
|
nr 2
199-217
EN
In this paper we translate Ramsey-type problems into the language of decomposable hereditary properties of graphs. We prove a distributive law for reducible and decomposable properties of graphs. Using it we establish some values of graph theoretical invariants of decomposable properties and show their correspondence to generalized Ramsey numbers.
6
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Graphs maximal with respect to hom-properties

51%
Kratochvíl J., Mihók P., Semanišin G.
Discussiones Mathematicae Graph Theory
|
1997
|
tom 17
|
nr 1
77-88
EN
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.
7
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Maximal graphs with respect to hereditary properties

51%
Broere I., Frick M., Semanišin G.
Discussiones Mathematicae Graph Theory
|
1997
|
tom 17
|
nr 1
51-66
EN
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.
8
Content available remote

Some Variations of Perfect Graphs

51%
Dettlaff M., Lemańska M., Semanišin G., Zuazua R.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 3
661-668
EN
We consider (ψk−γk−1)-perfect graphs, i.e., graphs G for which ψk(H) = γk−1(H) for any induced subgraph H of G, where ψk and γk−1 are the k-path vertex cover number and the distance (k − 1)-domination number, respectively. We study (ψk−γk−1)-perfect paths, cycles and complete graphs for k ≥ 2. Moreover, we provide a complete characterisation of (ψ2 − γ1)- perfect graphs describing the set of its forbidden induced subgraphs and providing the explicit characterisation of the structure of graphs belonging to this family.
9
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On universal graphs for hom-properties

51%
Mihók P., Miškuf J., Semanišin G.
Discussiones Mathematicae Graph Theory
|
2009
|
tom 29
|
nr 2
401-409
EN
A graph property is any isomorphism closed class of simple graphs. For a simple finite graph H, let → H denote the class of all simple countable graphs that admit homomorphisms to H, such classes of graphs are called hom-properties. Given a graph property 𝓟, a graph G ∈ 𝓟 is universal in 𝓟 if each member of 𝓟 is isomorphic to an induced subgraph of G. In particular, we consider universal graphs in → H and we give a new proof of the existence of a universal graph in → H, for any finite graph H.
10
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

A survey of hereditary properties of graphs

45%
Borowiecki M., Broere I., Frick M., Mihók P., Semanišin G.
Discussiones Mathematicae Graph Theory
|
1997
|
tom 17
|
nr 1
5-50
EN
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.
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ć.