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

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

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych:  hypergraph
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

Hajós' theorem for list colorings of hypergraphs

100%
Benzaken C., Gravier S., Skrekovski R.
Discussiones Mathematicae Graph Theory
|
2003
|
tom 23
|
nr 2
207-213
EN
A well-known theorem of Hajós claims that every graph with chromathic number greater than k can be constructed from disjoint copies of the complete graph $K_{k+1}$ by repeated application of three simple operations. This classical result has been extended in 1978 to colorings of hypergraphs by C. Benzaken and in 1996 to list-colorings of graphs by S. Gravier. In this note, we capture both variations to extend Hajós' theorem to list-colorings of hypergraphs.
2
Content available remote

A Characterization of Hypergraphs with Large Domination Number

100%
Henning M. A., Löwenstein C.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 2
427-438
EN
Let H = (V, E) be a hypergraph with vertex set V and edge set E. A dominating set in H is a subset of vertices D ⊆ V such that for every vertex v ∈ V \ D there exists an edge e ∈ E for which v ∈ e and e ∩ D ≠ ∅. The domination number γ(H) is the minimum cardinality of a dominating set in H. It is known [Cs. Bujtás, M.A. Henning and Zs. Tuza, Transversals and domination in uniform hypergraphs, European J. Combin. 33 (2012) 62-71] that for k ≥ 5, if H is a hypergraph of order n and size m with all edges of size at least k and with no isolated vertex, then γ(H) ≤ (n + ⌊(k − 3)/2⌋m)/(⌊3(k − 1)/2⌋). In this paper, we apply a recent result of the authors on hypergraphs with large transversal number [M.A. Henning and C. Löwenstein, A characterization of hypergraphs that achieve equality in the Chvátal-McDiarmid Theorem, Discrete Math. 323 (2014) 69-75] to characterize the hypergraphs achieving equality in this bound.
3
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Competition hypergraphs of digraphs with certain properties II. Hamiltonicity

100%
Sonntag M., Teichert H.-M.
Discussiones Mathematicae Graph Theory
|
2008
|
tom 28
|
nr 1
23-34
EN
If D = (V,A) is a digraph, its competition hypergraph 𝓒𝓗 (D) has vertex set V and e ⊆ V is an edge of 𝓒𝓗 (D) iff |e| ≥ 2 and there is a vertex v ∈ V, such that $e = N_D⁻(v) = {w ∈ V|(w,v) ∈ A}$. We give characterizations of 𝓒𝓗 (D) in case of hamiltonian digraphs D and, more general, of digraphs D having a τ-cycle factor. The results are closely related to the corresponding investigations for competition graphs in Fraughnaugh et al. [4] and Guichard [6].
4
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Directed hypergraphs: a tool for researching digraphs and hypergraphs

100%
Galeana-Sánchez H., Manrique M.
Discussiones Mathematicae Graph Theory
|
2009
|
tom 29
|
nr 2
313-335
EN
In this paper we introduce the concept of directed hypergraph. It is a generalisation of the concept of digraph and is closely related with hypergraphs. The basic idea is to take a hypergraph, partition its edges non-trivially (when possible), and give a total order to such partitions. The elements of these partitions are called levels. In order to preserve the structure of the underlying hypergraph, we ask that only vertices which belong to exactly the same edges may be in the same level of any edge they belong to. Some little adjustments are needed to avoid directed walks within a single edge of the underlying hypergraph, and to deal with isolated vertices. The concepts of independent set, absorbent set, and transversal set are inherited directly from digraphs. As a consequence of our results on this topic, we have found both a class of kernel-perfect digraphs with odd cycles and a class of hypergraphs which have a strongly independent transversal set.
5
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Competition hypergraphs of digraphs with certain properties I. Strong connectedness

100%
Sonntag M., Teichert H.-M.
Discussiones Mathematicae Graph Theory
|
2008
|
tom 28
|
nr 1
5-21
EN
If D = (V,A) is a digraph, its competition hypergraph 𝓒𝓗(D) has the vertex set V and e ⊆ V is an edge of 𝓒𝓗(D) iff |e| ≥ 2 and there is a vertex v ∈ V, such that e = {w ∈ V|(w,v) ∈ A}. We tackle the problem to minimize the number of strong components in D without changing the competition hypergraph 𝓒𝓗(D). The results are closely related to the corresponding investigations for competition graphs in Fraughnaugh et al. [3].
6
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Short paths in 3-uniform quasi-random hypergraphs

100%
Polcyn J.
Discussiones Mathematicae Graph Theory
|
2004
|
tom 24
|
nr 3
469-484
EN
Frankl and Rödl [3] proved a strong regularity lemma for 3-uniform hypergraphs, based on the concept of δ-regularity with respect to an underlying 3-partite graph. In applications of that lemma it is often important to be able to "glue" together separate pieces of the desired subhypergraph. With this goal in mind, in this paper it is proved that every pair of typical edges of the underlying graph can be connected by a hyperpath of length at most seven. The typicality of edges is defined in terms of graph and hypergraph neighborhoods, and it is shown that all but a small fraction of edges are indeed typical.
7
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Unique factorization theorem for object-systems

88%
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.
8
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On uniquely partitionable relational structures and object systems

88%
Bucko J., Mihók P.
Discussiones Mathematicae Graph Theory
|
2006
|
tom 26
|
nr 2
281-289
EN
We introduce object systems as a common generalization of graphs, hypergraphs, digraphs and relational structures. Let C be a concrete category, a simple object system over C is an ordered pair S = (V,E), where E = {A₁,A₂,...,Aₘ} is a finite set of the objects of C, such that the ground-set $V(A_i)$ of each object $A_i ∈ E$ is a finite set with at least two elements and $V ⊇ ⋃_{i=1}^m V(A_i)$. To generalize the results on graph colourings to simple object systems we define, analogously as for graphs, that an additive induced-hereditary property of simple object systems over a category C is any class of systems closed under isomorphism, induced-subsystems and disjoint union of systems, respectively. We present a survey of recent results and conditions for object systems to be uniquely partitionable into subsystems of given properties.
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ć.