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ę "hypergraphs" wg kryterium: Wszystkie pola

  Lista filtrów
Wyrównaj
Wyświetlanie 1-50 z 68
Tytuł:
A note of self-complementary hypergraphs
Autorzy:
Zwonek, M.
Powiązania:
https://bibliotekanauki.pl/articles/255199.pdf
Data publikacji:
2005
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
self-complementary hypergraphs
complementing permutation
Opis:
In the paper we describe all self-complementary hypergraphs. It turns out that such hypergraphs exist if and only if the number of vertices of the hypergraph is of the form n = 2k. This answers a conjecture posed by A. Szymański (see[3]).
Źródło:
Opuscula Mathematica; 2005, 25, 2; 351-354
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Sum labellings of cycle hypergraphs
Autorzy:
Teichert, Hanns-Martin
Powiązania:
https://bibliotekanauki.pl/articles/743801.pdf
Data publikacji:
2000
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
hypergraphs
sum number
vertex labelling
Opis:
A hypergraph is a sum hypergraph iff there are a finite S ⊆ IN⁺ and d̲, [d̅] ∈ IN⁺ with 1 < d̲ ≤ [d̅] such that is isomorphic to the hypergraph $_{d̲,[d̅]} (S) = (V,)$ where V = S and $ = {e ⊆ S:d̲ ≤ |e| ≤ [d̅] ∧ ∑_{v∈ e} v ∈ S}$. For an arbitrary hypergraph the sum number σ = σ() is defined to be the minimum number of isolated vertices $y₁,..., y_σ ∉ V$ such that $ ∪ {y₁,...,y_σ}$ is a sum hypergraph.
Generalizing the graph Cₙ we obtain d-uniform hypergraphs where any d consecutive vertices of Cₙ form an edge. We determine sum numbers and investigate properties of sum labellings for this class of cycle hypergraphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2000, 20, 2; 255-265
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Classes of hypergraphs with sum number one
Autorzy:
Teichert, Hanns-Martin
Powiązania:
https://bibliotekanauki.pl/articles/743701.pdf
Data publikacji:
2000
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
hypergraphs
sum number
vertex labelling
Opis:
A hypergraph ℋ is a sum hypergraph iff there are a finite S ⊆ ℕ⁺ and d̲,d̅ ∈ ℕ⁺ with 1 < d̲ < d̅ such that ℋ is isomorphic to the hypergraph $ℋ_{d̲,d̅}(S) = (V,)$ where V = S and $ = {e ⊆ S: d̲ < |e| < d̅ ∧ ∑_{v∈ e} v∈ S}$. For an arbitrary hypergraph ℋ the sum number(ℋ ) is defined to be the minimum number of isolatedvertices $w₁,..., w_σ∉ V$ such that $ℋ ∪ {w₁,..., w_σ}$ is a sum hypergraph.
For graphs it is known that cycles Cₙ and wheels Wₙ have sum numbersgreater than one. Generalizing these graphs we prove for the hypergraphs ₙ and ₙ that under a certain condition for the edgecardinalities (ₙ)= (ₙ)=1
Źródło:
Discussiones Mathematicae Graph Theory; 2000, 20, 1; 93-103
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Chromatic polynomials of hypergraphs
Autorzy:
Borowiecki, Mieczysław
Łazuka, Ewa
Powiązania:
https://bibliotekanauki.pl/articles/743817.pdf
Data publikacji:
2000
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
chromatic polynomial
chromatically unique hypergraphs
chromatic characterization
Opis:
In this paper we present some hypergraphs which are chromatically characterized by their chromatic polynomials. It occurs that these hypergraphs are chromatically unique. Moreover we give some equalities for the chromatic polynomials of hypergraphs generalizing known results for graphs and hypergraphs of Read and Dohmen.
Źródło:
Discussiones Mathematicae Graph Theory; 2000, 20, 2; 293-301
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
The sum number of d-partite complete hypergraphs
Autorzy:
Teichert, Hanns-Martin
Powiązania:
https://bibliotekanauki.pl/articles/744247.pdf
Data publikacji:
1999
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
sum number
sum hypergraphs
d-partite complete hypergraph
Opis:
A d-uniform hypergraph is a sum hypergraph iff there is a finite S ⊆ IN⁺ such that is isomorphic to the hypergraph $ ⁺_d(S) = (V,)$, where V = S and $ = {{v₁,...,v_d}: (i ≠ j ⇒ v_i ≠ v_j)∧ ∑^d_{i=1} v_i ∈ S}$. For an arbitrary d-uniform hypergraph the sum number σ = σ() is defined to be the minimum number of isolated vertices $w₁,...,w_σ ∉ V$ such that $ ∪{ w₁,..., w_σ}$ is a sum hypergraph.
In this paper, we prove
$σ(^{d}_{n₁,...,n_d}) = 1 + ∑^d_{i=1} (n_i -1 ) + min{0,⌈1/2(∑_{i=1}^{d-1} (n_i -1) - n_d)⌉}$,
where $^{d}_{n₁,...,n_d}$ denotes the d-partite complete hypergraph; this generalizes the corresponding result of Hartsfield and Smyth [8] for complete bipartite graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 1999, 19, 1; 79-91
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Maximal hypergraphs with respect to the bounded cost hereditary property
Autorzy:
Drgas-Burchardt, Ewa
Fiedorowicz, Anna
Powiązania:
https://bibliotekanauki.pl/articles/744307.pdf
Data publikacji:
2005
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
cost colouring
hereditary property
maximal hypergraphs
Opis:
The hereditary property of hypergraphs generated by the cost colouring notion is considered in the paper. First, we characterize all maximal graphs with respect to this property. Second, we give the generating function for the sequence describing the number of such graphs with the numbered order. Finally, we construct a maximal hypergraph for each admissible number of vertices showing some density property. All results can be applied to the problem of information storage.
Źródło:
Discussiones Mathematicae Graph Theory; 2005, 25, 1-2; 67-77
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Directed hypergraphs: a tool for researching digraphs and hypergraphs
Autorzy:
Galeana-Sánchez, Hortensia
Manrique, Martín
Powiązania:
https://bibliotekanauki.pl/articles/743191.pdf
Data publikacji:
2009
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
hypergraph
strongly independent set
transversal set
kernel
Opis:
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.
Źródło:
Discussiones Mathematicae Graph Theory; 2009, 29, 2; 313-335
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
About uniquely colorable mixed hypertrees
Autorzy:
Niculitsa, Angela
Voloshin, Vitaly
Powiązania:
https://bibliotekanauki.pl/articles/743697.pdf
Data publikacji:
2000
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
colorings of graphs and hypergraphs
mixed hypergraphs
unique colorability
trees
hypertrees
elimination ordering
Opis:
A mixed hypergraph is a triple = (X,,) where X is the vertex set and each of , is a family of subsets of X, the -edges and -edges, respectively. A k-coloring of is a mapping c: X → [k] such that each -edge has two vertices with the same color and each -edge has two vertices with distinct colors. = (X,,) is called a mixed hypertree if there exists a tree T = (X,) such that every -edge and every -edge induces a subtree of T. A mixed hypergraph is called uniquely colorable if it has precisely one coloring apart from permutations of colors. We give the characterization of uniquely colorable mixed hypertrees.
Źródło:
Discussiones Mathematicae Graph Theory; 2000, 20, 1; 81-91
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Self-complementary hypergraphs
Autorzy:
Wojda, A.
Powiązania:
https://bibliotekanauki.pl/articles/743928.pdf
Data publikacji:
2006
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
k-uniform hypergraph
self-complementary hypergraph
Opis:
A k-uniform hypergraph H = (V;E) is called self-complementary if there is a permutation σ:V → V, called self-complementing, such that for every k-subset e of V, e ∈ E if and only if σ(e) ∉ E. In other words, H is isomorphic with $H' = (V; \binom{V}{k} - E)$.
In the present paper, for every k, (1 ≤ k ≤ n), we give a characterization of self-complementig permutations of k-uniform self-complementary hypergraphs of the order n. This characterization implies the well known results for self-complementing permutations of graphs, given independently in the years 1962-1963 by Sachs and Ringel, and those obtained for 3-uniform hypergraphs by Kocay, for 4-uniform hypergraphs by Szymański, and for general (not uniform) hypergraphs by Zwonek.
Źródło:
Discussiones Mathematicae Graph Theory; 2006, 26, 2; 217-224
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Subgraph densities in hypergraphs
Autorzy:
Peng, Yuejian
Powiązania:
https://bibliotekanauki.pl/articles/743780.pdf
Data publikacji:
2007
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Erdös jumping constant conjecture
Lagrangian
optimal vector
Opis:
Let r ≥ 2 be an integer. A real number α ∈ [0,1) is a jump for r if for any ε > 0 and any integer m ≥ r, any r-uniform graph with n > n₀(ε,m) vertices and density at least α+ε contains a subgraph with m vertices and density at least α+c, where c = c(α) > 0 does not depend on ε and m. A result of Erdös, Stone and Simonovits implies that every α ∈ [0,1) is a jump for r = 2. Erdös asked whether the same is true for r ≥ 3. Frankl and Rödl gave a negative answer by showing an infinite sequence of non-jumps for every r ≥ 3. However, there are still a lot of open questions on determining whether or not a number is a jump for r ≥ 3. In this paper, we first find an infinite sequence of non-jumps for r = 4, then extend one of them to every r ≥ 4. Our approach is based on the techniques developed by Frankl and Rödl.
Źródło:
Discussiones Mathematicae Graph Theory; 2007, 27, 2; 281-297
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Short paths in 3-uniform quasi-random hypergraphs
Autorzy:
Polcyn, Joanna
Powiązania:
https://bibliotekanauki.pl/articles/744576.pdf
Data publikacji:
2004
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
hypergraph
path
quasi-randomness
Opis:
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.
Źródło:
Discussiones Mathematicae Graph Theory; 2004, 24, 3; 469-484
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A note on a list colouring of hypergraphs
Autorzy:
Drgas-Burchardt, E.
Powiązania:
https://bibliotekanauki.pl/articles/2050379.pdf
Data publikacji:
2004
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
hypergraph
list colouring
Opis:
In the note we present two results. The first of them gives a sufficient condition for a colouring of a hypergraph from an assigned list. It generalises the analogous fact for graphs. The second result states that for every $k \geq 3$ and every $l \geq 2$, a distance between the list chromatic number and the chromatic number can be arbitrarily large in the class of k-uniform hypergraphs with the chromatic number bounded below by l. A similar result for k-uniform, 2-colorable hypergraphs is known but the proof techniques are different.
Źródło:
Opuscula Mathematica; 2004, 24, 2; 171-175
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A Note on Packing of Uniform Hypergraphs
Autorzy:
Konarski, Jerzy
Woźniak, Mariusz
Żak, Andrzej
Powiązania:
https://bibliotekanauki.pl/articles/32222532.pdf
Data publikacji:
2022-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
packing
hypergraphs
Opis:
We say that two n-vertex hypergraphs H1 and H2 pack if they can be found as edge-disjoint subhypergraphs of the complete hypergraph Kn. Whilst the problem of packing of graphs (i.e., 2-uniform hypergraphs) has been studied extensively since seventies, much less is known about packing of k-uniform hypergraphs for k ≥ 3. Naroski [Packing of nonuniform hypergraphs - product and sum of sizes conditions, Discuss. Math. Graph Theory 29 (2009) 651–656] defined the parameter mk(n) to be the smallest number m such that there exist two n-vertex k-uniform hypergraphs with total number of edges equal to m which do not pack, and conjectured that mk(n) = Θ (nk−1). In this note we show that this conjecture is far from being truth. Namely, we prove that the growth rate of mk(n) is of order nk/2 exactly for even k’s and asymptotically for odd k’s.
Źródło:
Discussiones Mathematicae Graph Theory; 2022, 42, 4; 1383-1388
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Subdivision of hypergraphs and their colorings
Autorzy:
Iradmusa, Moharram N.
Powiązania:
https://bibliotekanauki.pl/articles/255017.pdf
Data publikacji:
2020
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
hypergraph
uniform hypergraph
subdivision of hypergraph
Opis:
In this paper we introduce the subdivision of hypergraphs, study their properties and parameters and investigate their weak and strong chromatic numbers in various cases.
Źródło:
Opuscula Mathematica; 2020, 40, 2; 271-290
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Packing of nonuniform hypergraphs - product and sum of sizes conditions
Autorzy:
Naroski, Paweł
Powiązania:
https://bibliotekanauki.pl/articles/744492.pdf
Data publikacji:
2009
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
nonuniform hypergraph
packing
Opis:
Hypergraphs $H₁,...,H_N$ of order n are mutually packable if one can find their edge disjoint copies in the complete hypergraph of order n. We prove that two hypergraphs are mutually packable if the product of their sizes satisfies some upper bound. Moreover we show that an arbitrary set of the hypergraphs is mutually packable if the sum of their sizes is sufficiently small.
Źródło:
Discussiones Mathematicae Graph Theory; 2009, 29, 3; 651-656
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Domination hypergraphs of certain digraphs
Autorzy:
Sonntag, M.
Teichert, H. M.
Powiązania:
https://bibliotekanauki.pl/articles/254767.pdf
Data publikacji:
2010
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
hypergraph
dominating set
directed graph
Opis:
If D = (V,A) is a digraph, its domination hypergraph DH(D) = (V, E) has the vertex set V and e ⊆ V is an edge of DH(D) if and only if e is a minimal dominating set of D. We investigate domination hypergraphs of special classes of digraphs, namely tournaments, paths and cycles. Finally, using a special decomposition/composition method we construct edge sets of domination hypergraphs of certain digraphs.
Źródło:
Opuscula Mathematica; 2010, 30, 2; 179-191
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Maximum Hypergraphs without Regular Subgraphs
Autorzy:
Kim, Jaehoon
Kostochka, Alexandr V.
Powiązania:
https://bibliotekanauki.pl/articles/30147226.pdf
Data publikacji:
2014-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
hypergraphs
set system
subgraph
regular graph
Opis:
We show that an n-vertex hypergraph with no r-regular subgraphs has at most $2^{n−1}+r−2$ edges. We conjecture that if n > r, then every n-vertex hypergraph with no r-regular subgraphs having the maximum number of edges contains a full star, that is, $2^{n−1}$ distinct edges containing a given vertex. We prove this conjecture for n ≥ 425. The condition that n > r cannot be weakened.
Źródło:
Discussiones Mathematicae Graph Theory; 2014, 34, 1; 151-166
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Constrained Colouring and σ-Hypergraphs
Autorzy:
Caro, Yair
Lauri, Josef
Zarb, Christina
Powiązania:
https://bibliotekanauki.pl/articles/31339148.pdf
Data publikacji:
2015-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
σ-hypergraphs
constrained colourings
hypergraph colourings
Opis:
A constrained colouring or, more specifically, an $(\alpha, \beta)$-colouring of a hypergraph $H$, is an assignment of colours to its vertices such that no edge of $H$ contains less than $\alpha$ or more than $\beta$ vertices with different colours. This notion, introduced by Bujtás and Tuza, generalises both classical hypergraph colourings and more general Voloshin colourings of hypergraphs. In fact, for $r$-uniform hypergraphs, classical colourings correspond to $(2, r)$-colourings while an important instance of Voloshin colourings of $r$-uniform hypergraphs gives $(2, r−1)$-colourings. One intriguing aspect of all these colourings, not present in classical colourings, is that $H$ can have gaps in its $(\alpha, \beta)$-spectrum, that is, for $k_1 < k_2 < k_3$, $H$ would be $(\alpha, \beta)$-colourable using $k_1$ and using $k_3$ colours, but not using $k_2$ colours. In an earlier paper, the first two authors introduced, for $\sigma$ being a partition of $r$, a very versatile type of $r$-uniform hypergraph which they called $\sigma$-hypergraphs. They showed that, by simple manipulation of the parameters of a $\sigma$-hypergraph $H$, one can obtain families of hypergraphs which have $(2, r − 1)$-colourings exhibiting various interesting chromatic properties. They also showed that, if the smallest part of $\sigma$ is at least 2, then $H$ will never have a gap in its $(2, r − 1)$-spectrum but, quite surprisingly, they found examples where gaps re-appear when $\alpha = \beta = 2$. In this paper we extend many of the results of the first two authors to more general $(\alpha, \beta)$-colourings, and we study the phenomenon of the disappearance and re-appearance of gaps and show that it is not just the behaviour of a particular example but we place it within the context of a more general study of constrained colourings of $\sigma$-hypergraphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2015, 35, 1; 171-189
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A note on packing of two copies of a hypergraph
Autorzy:
Pilśniak, Monika
Woźniak, Mariusz
Powiązania:
https://bibliotekanauki.pl/articles/743647.pdf
Data publikacji:
2007
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
packing
hypergraphs
Opis:
A 2-packing of a hypergraph is a permutation σ on V() such that if an edge e belongs to (), then σ (e) does not belong to ().
We prove that a hypergraph which does not contain neither empty edge ∅ nor complete edge V() and has at most 1/2n edges is 2-packable.
A 1-uniform hypergraph of order n with more than 1/2n edges shows that this result cannot be improved by increasing the size of .
Źródło:
Discussiones Mathematicae Graph Theory; 2007, 27, 1; 45-49
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
The representation of multi-hypergraphs by set intersections
Autorzy:
Bylka, Stanisław
Komar, Jan
Powiązania:
https://bibliotekanauki.pl/articles/743464.pdf
Data publikacji:
2007
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
intersection graph
intersection hypergraph
Opis:
This paper deals with weighted set systems (V,,q), where V is a set of indices, $ ⊂ 2^V$ and the weight q is a nonnegative integer function on . The basic idea of the paper is to apply weighted set systems to formulate restrictions on intersections. It is of interest to know whether a weighted set system can be represented by set intersections. An intersection representation of (V,,q) is defined to be an indexed family $R = (R_v)_{v∈ V}$ of subsets of a set S such that
$|⋂_{v∈ E} R_v| = q(E)$ for each E ∈ .
A necessary condition for the existence of such representation is the monotonicity of q on i.e., if F ⊂ then q(F) ≥ q(). Some sufficient conditions for weighted set systems representable by set intersections are given. Appropriate existence theorems are proved by construction of the solutions. The notion of intersection multigraphs to intersection multi- hypergraphs - hypergraphs with multiple edges, is generalized. Some conditions for intersection multi-hypergraphs are formulated.
Źródło:
Discussiones Mathematicae Graph Theory; 2007, 27, 3; 565-582
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Recursion Relations for Chromatic Coefficients for Graphs and Hypergraphs
Autorzy:
Durhuus, Bergfinnur
Lucia, Angelo
Powiązania:
https://bibliotekanauki.pl/articles/32361749.pdf
Data publikacji:
2022-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
chromatic polynomials
hypergraphs
broken cycles
Opis:
We establish a set of recursion relations for the coefficients in the chromatic polynomial of a graph or a hypergraph. As an application we provide a generalization of Whitney’s broken cycle theorem for hypergraphs, as well as deriving an explicit formula for the linear coefficient of the chromatic polynomial of the r-complete hypergraph in terms of roots of the Taylor polynomials for the exponential function.
Źródło:
Discussiones Mathematicae Graph Theory; 2022, 42, 1; 101-121
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A note on a broken-cycle theorem for hypergraphs
Autorzy:
Trinks, Martin
Powiązania:
https://bibliotekanauki.pl/articles/31231998.pdf
Data publikacji:
2014-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Broken-cycle Theorem
hypergraphs
cycles
chromatic polynomial
graph polynomials
Opis:
Whitney’s Broken-cycle Theorem states the chromatic polynomial of a graph as a sum over special edge subsets. We give a definition of cycles in hypergraphs that preserves the statement of the theorem there.
Źródło:
Discussiones Mathematicae Graph Theory; 2014, 34, 3; 641-646
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Hajós theorem for list colorings of hypergraphs
Autorzy:
Benzaken, Claude
Gravier, Sylvain
Skrekovski, Riste
Powiązania:
https://bibliotekanauki.pl/articles/743401.pdf
Data publikacji:
2003
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
list-coloring
Hajós' construction
hypergraph
Opis:
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.
Źródło:
Discussiones Mathematicae Graph Theory; 2003, 23, 2; 207-213
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A note on self-complementary 4-uniform hypergraphs
Autorzy:
Szymański, A.
Powiązania:
https://bibliotekanauki.pl/articles/255191.pdf
Data publikacji:
2005
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
complementing permutation
self-complementary hypergraph
k-uniform hypergraph
Opis:
We prove that a permutation theta is complementing permutation for a 4-uniform hypergraph if and only if one of the following cases is satisfied: (i) the length of every cycle of theta is a multiple of 8, (ii) theta has 1, 2 or 3 fixed points, and all other cycles have length a multiple of 8, (iii) theta has 1 cycle of length 2, and all other cycles have length a multiple of 8, (iv) theta has 1 fixed point, 1 cycle of length 2, and all other cycles have length a multiple of 8, (v) theta has 1 cycle of length 3, and all other cycles have length a multiple of 8. Moreover, we present algorithms for generating every possible 3 and 4-uniform self-complementary hypergraph.
Źródło:
Opuscula Mathematica; 2005, 25, 2; 319-323
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On Marczewski-Steinhaus type distance between hypergraphs
O odległości typu Marczewskiego-Steinhausa między hipergrafami
Autorzy:
Karoński, M.
Palka, Z.
Powiązania:
https://bibliotekanauki.pl/articles/740824.pdf
Data publikacji:
1977
Wydawca:
Polska Akademia Nauk. Instytut Matematyczny PAN
Źródło:
Applicationes Mathematicae; 1977-1980, 16, 1; 47-57
1233-7234
Pojawia się w:
Applicationes Mathematicae
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Competition hypergraphs of digraphs with certain properties II. Hamiltonicity
Autorzy:
Sonntag, Martin
Teichert, Hanns-Martin
Powiązania:
https://bibliotekanauki.pl/articles/743489.pdf
Data publikacji:
2008
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
hypergraph
competition graph
hamiltonian digraph
Opis:
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].
Źródło:
Discussiones Mathematicae Graph Theory; 2008, 28, 1; 23-34
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Decompositions of complete 3-uniform hypergraphs into cycles of constant prime length
Autorzy:
Lakshmi, R
Poovaragavan, T.
Powiązania:
https://bibliotekanauki.pl/articles/255686.pdf
Data publikacji:
2020
Wydawca:
Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:
uniform hypergraph
cycle decomposition
Opis:
A complete 3-unilorm hypergraph of order n has vertex set V with \V\ = n and the set ol all 3-subsets of V as its edge set. A t-cycle in this hypergraph is v1, e1, v2, e2,… , vt, et, v1 where v1, v2,…vt are distinct vertices and e1, e-2,..., et are distinct edges such that [formula] and [formula] A decomposition of a hypergraph is a partition of its edge set into edge-disjoint subsets. In this paper, we give necessary and sufficient conditions for a decomposition of the complete 3-unilorm hypergraph of order n into p-cycles, whenever p is prime.
Źródło:
Opuscula Mathematica; 2020, 40, 4; 509-516
1232-9274
2300-6919
Pojawia się w:
Opuscula Mathematica
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
The size of minimum 3-trees: cases 0 and 1 mod 12
Autorzy:
Arocha, Jorge
Tey, Joaquín
Powiązania:
https://bibliotekanauki.pl/articles/743397.pdf
Data publikacji:
2003
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
tight hypergraphs
triple systems
Opis:
A 3-uniform hypergraph is called a minimum 3-tree, if for any 3-coloring of its vertex set there is a heterochromatic triple and the hypergraph has the minimum possible number of triples. There is a conjecture that the number of triples in such 3-tree is ⎡(n(n-2))/3⎤ for any number of vertices n. Here we give a proof of this conjecture for any n ≡ 0,1 mod 12.
Źródło:
Discussiones Mathematicae Graph Theory; 2003, 23, 1; 177-187
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Competition hypergraphs of digraphs with certain properties I. Strong connectedness
Autorzy:
Sonntag, Martin
Teichert, Hanns-Martin
Powiązania:
https://bibliotekanauki.pl/articles/743493.pdf
Data publikacji:
2008
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
hypergraph
competition graph
strong component
Opis:
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].
Źródło:
Discussiones Mathematicae Graph Theory; 2008, 28, 1; 5-21
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Analysis of the efficiency of graph coloring algorithms
Autorzy:
Kubale, Marek
Powiązania:
https://bibliotekanauki.pl/articles/748571.pdf
Data publikacji:
1982
Wydawca:
Polskie Towarzystwo Matematyczne
Tematy:
Computational complexity and efficiency of algorithms
Coloring of graphs and hypergraphs
Graph theory
Opis:
.
This paper discusses the computational efficiency and the number of colors used by the following algorithms for coloring vertices of graphs: sequential coloring and sequential coloring with interchange algorithms for a largest-first and a smallest-last orderings of vertices, the coloring-pairs algorithm, and the approximately maximum independent set algorithm. Each algorithm is supplied with a Pascal-like program, time complexity in terms of the size of a graph, and worst-case behaviour. In conclusion, some computational results are included with support the estimations and suggest the sequential coloring with interchange algorithm for a largest-first vertex ordering as a method which uses the least number of colors for uniformly distributed random graphs.
Źródło:
Mathematica Applicanda; 1982, 10, 19
1730-2668
2299-4009
Pojawia się w:
Mathematica Applicanda
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Sum-List Colouring of Unions of a Hypercycle and a Path with at Most Two Vertices in Common
Autorzy:
Drgas-Burchardt, Ewa
Sidorowicz, Elżbieta
Powiązania:
https://bibliotekanauki.pl/articles/31527293.pdf
Data publikacji:
2020-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
hypergraphs
sum-list colouring
induced hereditary classes
forbidden hypergraphs
Opis:
Given a hypergraph \(\mathcal{H}\) and a function \(f : V (\mathcal{H}) → ℕ\), we say that \(\mathcal{H}\) is $f$-choosable if there is a proper vertex colouring $ϕ$ of \(\mathcal{H}\) such that $ϕ (v) ∈ L(v)$ for all \(v ∈ V (\mathcal{H})\), where \(L : V (\mathcal{H}) → 2^ℕ\) is any assignment of $f(v)$ colours to a vertex $v$. The sum choice number \(\mathcal{H}i_{sc}(\mathcal{H})\) of \(\mathcal{H}\) is defined to be the minimum of \(Σ_{v∈V(\mathcal{H})}f(v)\) over all functions $f$ such that \(\mathcal{H}\) is $f$-choosable. For an arbitrary hypergraph \(\mathcal{H}\) the inequality \(χ_{sc}(\mathcal{H}) ≤ |V (\mathcal{H})| + |ɛ (\mathcal{H})|\) holds, and hypergraphs that attain this upper bound are called $sc$-greedy. In this paper we characterize $sc$-greedy hypergraphs that are unions of a hypercycle and a hyperpath having at most two vertices in common. Consequently, we characterize the hypergraphs of this type that are forbidden for the class of $sc$-greedy hypergraphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2020, 40, 3; 893-917
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Automatyczny system wspomagający proces projektowania systemów dyskretnych z wykorzystaniem hipergrafów
CAD system for automatic decomposition of discrete systems based on hypergraphs
Autorzy:
Wiśniewska, M.
Powiązania:
https://bibliotekanauki.pl/articles/156956.pdf
Data publikacji:
2011
Wydawca:
Stowarzyszenie Inżynierów i Techników Mechaników Polskich
Tematy:
graf
hipergraf
dekompozycja systemów dyskretnych
autorski system wspomagający proces dekompozycji systemów dyskretnych z wykorzystaniem hipergrafów (system Hippo)
graph
hypergraph
decomposition of discrete system
CAD system Hippo for automatic decomposition of Petri Nets based on hypergraphs
Opis:
W artykule zaprezentowany został autorski system wspomagający proces projektowania systemów dyskretnych z wykorzystaniem hipergrafów. Narzędzie Hippo składa się ze zbioru bibliotek, realizujących najważniejsze operacje z zakresu teorii grafów i hipergrafów (m. in. kolorowanie, pokrycie, dopełnienie, dualizm, itd.), które zostały zrealizowane pod kątem ich zastosowania w dekompozycji systemów dyskretnych. Głównym zadaniem systemu jest usprawnienie oraz automatyzacja procesu dekompozycji systemów dyskretnych stosowanych m.in. w projektowaniu zaawansowanych układów cyfrowych (redukcja rozmiaru pamięci, selekcja klas kompatybilności, minimalizacja funkcji logicznych, dekompozycja automatów cyfrowych). Opracowany system Hippo umożliwia przeprowadzenie automatycznego procesu dekompozycji z zastosowaniem różnych algorytmów (zarówno grafowych, jak i hipergrafowych), w efekcie pozwalając wybrać użytkownikowi najkorzystniejsze rozwiązanie.
In the paper a dedicated CAD system Hippo for automatic decomposition of discrete systems is presented. The tool consists of a set of libraries. Each library was designed as a separate module to solve the particular problem from the field of the graph and hypergraph theories (among others: vertex coloring, vertex covering, transversal computation, dualism, computation of the graph and hypergraph complement). The main task of the system is to improve the process of decomposition of discrete systems (for example: reduction of the microinstruction length, selection of the compatibility classes, decomposition of concurrent automata). The Hippo system consists of eight main modules:- complement -calculation of graph/hypergraph complement;- coloring - five methods of coloring of graph and hypergraph (four greedy and one backtracking);- transversal - four methods of transversals computation (fast reduction algorithm, greedy, backtracking, mixed fast reduction and greedy);- exact transversals - the calculation of the exact transversals is based on the Knuth DLX algorithm, the main advantage of such a solution is polynomial computational time in case of exact hypergraphs;- dualism (only for hypergraphs) - calculates the dual hypergraph;- converting graph to hypergraph;- converting hypergraph to graph;- conversion of the graph/hypergraph description to the TeX format.In the paper particular libraries are described in detail. Moreover, the stand-alone application (Hippo) is shown. Finally, an example of automatic decomposition of the discrete system is presented. All steps and required operations are described.
Źródło:
Pomiary Automatyka Kontrola; 2011, R. 57, nr 7, 7; 726-728
0032-4140
Pojawia się w:
Pomiary Automatyka Kontrola
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Dichromatic number, circulant tournaments and Zykov sums of digraphs
Autorzy:
Neumann-Lara, Víctor
Powiązania:
https://bibliotekanauki.pl/articles/743771.pdf
Data publikacji:
2000
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
digraphs
dichromatic number
vertex-critical
Zykov sums
tournaments
circulant
covering numbers in hypergraphs
Opis:
The dichromatic number dc(D) of a digraph D is the smallest number of colours needed to colour the vertices of D so that no monochromatic directed cycle is created. In this paper the problem of computing the dichromatic number of a Zykov-sum of digraphs over a digraph D is reduced to that of computing a multicovering number of an hypergraph H₁(D) associated to D in a natural way. This result allows us to construct an infinite family of pairwise non isomorphic vertex-critical k-dichromatic circulant tournaments for every k ≥ 3, k ≠ 7.
Źródło:
Discussiones Mathematicae Graph Theory; 2000, 20, 2; 197-207
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Majority-Vote Model on Scale-Free Hypergraphs
Autorzy:
Gradowski, T.
Krawiecki, A.
Powiązania:
https://bibliotekanauki.pl/articles/1388421.pdf
Data publikacji:
2015-03
Wydawca:
Polska Akademia Nauk. Instytut Fizyki PAN
Tematy:
89.75.Hc
64.60.Cn
05.10.Ln
05.50.+q
64.60.F-
Opis:
Majority-vote models on scale-free hypergraphs are investigated by means of numerical simulations with different variants of system dynamics. Hypergraphs are generalisations of ordinary graphs in which higher order of social organisation is included by introducing hyperedges corresponding to social groups, connecting more than two nodes. In the models under study, opinions of agents (two-state spins) placed in nodes are updated according to a probabilistic rule with control parameter representing social noise. The probability of a single spin flip depends on the average opinion within only one social group (hyperedge) the agent belongs to. This introduces an intermediate level of social interactions, in contrast with the case of networks, where the opinion of an agent usually depends on the average opinion of all neighbours. In all cases under consideration a second-order phase transition to a state with an uniform opinion was found as a function of the social noise, with the critical value of the control parameter and the critical exponents depending on the hypergraph topology and details of the system dynamics (node or hyperedge update).
Źródło:
Acta Physica Polonica A; 2015, 127, 3A; A-55-A-58
0587-4246
1898-794X
Pojawia się w:
Acta Physica Polonica A
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A note on k-uniform self-complementary hypergraphs of given order
Autorzy:
Szymański, Artur
Wojda, A.
Powiązania:
https://bibliotekanauki.pl/articles/743151.pdf
Data publikacji:
2009
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
self-complementing permutation
self-complementary hypergraph
k-uniform hypergraph
binomial coefficients
Opis:
We prove that a k-uniform self-complementary hypergraph of order n exists, if and only if $\binom{n}{k}$ is even.
Źródło:
Discussiones Mathematicae Graph Theory; 2009, 29, 1; 199-202
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Dekompozycja systemów dyskretnych z wykorzystaniem hipergrafów
Usage of hypergraphs in decomposition of discrete system
Autorzy:
Wiśniewska, M.
Wiśniewski, R.
Adamski, M.
Powiązania:
https://bibliotekanauki.pl/articles/152819.pdf
Data publikacji:
2007
Wydawca:
Stowarzyszenie Inżynierów i Techników Mechaników Polskich
Tematy:
system dyskretny
dekompozycja
hipergraf
discrete system
decomposition
hypergraph
Opis:
W referacie zaprezentowana zostanie metoda dekompozycji systemów dyskretnych z wykorzystaniem hipergrafów. Podział uzyskano poprzez zastosowanie hierarchicznej redukcji wierzchołków hipergrafu. W procesie partycjonowania bloki systemu dyskretnego reprezentowane są poprzez wierzchołki hipergrafu, natomiast połączenia pomiędzy blokami - poprzez hiperkrawędzie. Przedstawiona metoda umożliwia sekwencyjną redukcję wierzchołków hipergrafu, w których projektant sam może zadecydować, na którym poziomie hierarchii chce zakończyć partycjonowanie. Dzięki temu dany system może zostać podzielony na dowolną liczbę mniejszych układów.
In the paper a method of discrete-system decomposition is proposed. The method is based on the hypergraph reduction and partition. A discrete-system is represented by a hypergraph; where module corresponds to the vertice and connection (net) corresponds to the hyperedge. The proposed method allows hierarchical reduction of the hypergraph and finally - partition of the discrete-system.
Źródło:
Pomiary Automatyka Kontrola; 2007, R. 53, nr 5, 5; 129-131
0032-4140
Pojawia się w:
Pomiary Automatyka Kontrola
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Dekompozycja systemów dyskretnych poprzez zastosowanie hierarchicznej redukcji krawędzi hipergrafów
Usage of hypergraphs in hierarchical decomposition of discrete system
Autorzy:
Wiśniewska, M.
Adamski, M.
Powiązania:
https://bibliotekanauki.pl/articles/156242.pdf
Data publikacji:
2008
Wydawca:
Stowarzyszenie Inżynierów i Techników Mechaników Polskich
Tematy:
system dyskretny
dekompozycja
hipergraf
discrete system
decomposition
hypergraph
Opis:
W artykule zaproponowana zostanie metoda podziału systemu dyskretnego z wykorzystaniem teorii hipergrafów. System dyskretny reprezentowany jest poprzez hipergraf. Poszczególne moduły odzwierciedlane są poprzez wierzchołki, natomiast połączenia pomiędzy modułami - poprzez hiperkrawędzie. Tak określony system dyskretny może zostać poddany procesowi dekompozycji z wykorzystaniem teorii hipergrafów. Metoda podziału systemów dyskretnych z wykorzystaniem hipergrafów zostanie zilustrowana przykładem. Szczegółowo przedstawione zostaną wszystkie kroki, jakie są niezbędne do wykonania procesu dekompozycji hipergrafów.
A new method of the discrete-system decomposition is proposed in the paper. The method is based on the hypergraph reduction and partition. A discrete-system is represented by a hypergraph; where module corresponds to the vertex and connection (net) corresponds to the hyperedge. The proposed method allows hierarchical reduction of the hypergraph and finally - partition of the discrete-system. All steps that are required in order to perform the decomposition of the discreete -system will be shown. The method of the hierarchical reduction and partition of hypergraphs will be illustrated by an example.
Źródło:
Pomiary Automatyka Kontrola; 2008, R. 54, nr 8, 8; 517-519
0032-4140
Pojawia się w:
Pomiary Automatyka Kontrola
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Color-bounded hypergraphs, V: host graphs and subdivisions
Autorzy:
Bujtás, Csilla
Tuza, Zsolt
Voloshin, Vitaly
Powiązania:
https://bibliotekanauki.pl/articles/743863.pdf
Data publikacji:
2011
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
mixed hypergraph
color-bounded hypergraph
vertex coloring
arboreal hypergraph
hypertree
feasible set
host graph
edge subdivision
Opis:
A color-bounded hypergraph is a hypergraph (set system) with vertex set X and edge set = {E₁,...,Eₘ}, together with integers $s_i$ and $t_i$ satisfying $1 ≤ s_i ≤ t_i ≤ |E_i|$ for each i = 1,...,m. A vertex coloring φ is proper if for every i, the number of colors occurring in edge $E_i$ satisfies $s_i ≤ |φ(E_i)| ≤ t_i$. The hypergraph ℋ is colorable if it admits at least one proper coloring.
We consider hypergraphs ℋ over a "host graph", that means a graph G on the same vertex set X as ℋ, such that each $E_i$ induces a connected subgraph in G. In the current setting we fix a graph or multigraph G₀, and assume that the host graph G is obtained by some sequence of edge subdivisions, starting from G₀.
The colorability problem is known to be NP-complete in general, and also when restricted to 3-uniform "mixed hypergraphs", i.e., color-bounded hypergraphs in which $|E_i| = 3$ and $1 ≤ s_i ≤ 2 ≤ t_i ≤ 3$ holds for all i ≤ m. We prove that for every fixed graph G₀ and natural number r, colorability is decidable in polynomial time over the class of r-uniform hypergraphs (and more generally of hypergraphs with $|E_i| ≤ r$ for all 1 ≤ i ≤ m) having a host graph G obtained from G₀ by edge subdivisions. Stronger bounds are derived for hypergraphs for which G₀ is a tree.
Źródło:
Discussiones Mathematicae Graph Theory; 2011, 31, 2; 223-238
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Almost Self-Complementary Uniform Hypergraphs
Autorzy:
Wojda, Adam Paweł
Powiązania:
https://bibliotekanauki.pl/articles/31342288.pdf
Data publikacji:
2018-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
uniform hypergraph
Opis:
A $k$-uniform hypergraph ($k$-hypergraph) is almost self-complementary if it is isomorphic with its complement in the complete $k$-uniform hypergraph minus one edge. We prove that an almost self-complementary $k$-hypergraph of order $n$ exists if and only if \( \binom{n}{k} \) is odd.
Źródło:
Discussiones Mathematicae Graph Theory; 2018, 38, 2; 607-610
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Niche Hypergraphs
Autorzy:
Garske, Christian
Sonntag, Martin
Teichert, Hanns-Martin
Powiązania:
https://bibliotekanauki.pl/articles/31340768.pdf
Data publikacji:
2016-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
niche hypergraph
niche number
Opis:
If D = (V,A) is a digraph, its niche hypergraph Nℋ(D) = (V, ℰ) has the edge set ℰ = {ℯ ⊆ V | |e| ≥ 2 ∧ ∃ v ∈ V : e = ND-(v) ∨ ℯ = ND+(v)}. Niche hypergraphs generalize the well-known niche graphs (see [11]) and are closely related to competition hypergraphs (see [40]) as well as double competition hypergraphs (see [33]). We present several properties of niche hypergraphs of acyclic digraphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 4; 819-832
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Analysis of beam hypergraphs by means of exact and approximate methods as models of transverse vibrating subsystems in the synthesis of mechanical and mechatronic systems
Hipergrafy belek analizowanych metodą dokładną i przybliżoną jako modele podukładów drgających giętnie w syntezie układów mechanicznych i mechatronicznych
Autorzy:
Buchacz, A.
Powiązania:
https://bibliotekanauki.pl/articles/140054.pdf
Data publikacji:
2010
Wydawca:
Polska Akademia Nauk. Czytelnia Czasopism PAN
Tematy:
analiza hipergrafów belek
metoda dokładna
metoda przybliżona
metoda Galerkina
modelowanie
graf
system mechaniczny
system mechatroniczny
system drgający
analysis of beam hypergraphs
exact method
approximated method
Galerkin's method
modelling
graph
mechanical system
mechatronical system
vibrating system
Opis:
In this paper, the author compares of the characteristics of subsystems obtained by the approximate and exact method in order to answer to the question - if the approximate method can be used to nominate the characteristics of mechatronic systems. Frequency - modal analysis has been presented for a mechanical system, i.e. transverse-vibrating clamped-free beam. Consequently, the model of the beam was presented in a five-vertex hypergraph. This model, in the case of approximate frequency-modal analysis, can be imitated in a three-vertex hypergraph. Such formulation could be the introduction to synthesis of transverse-vibrating complex beam systems with constant cross-section.
W pracy porównano charakterystyki podukładów otrzymanych metodą przybliżoną i dokładną, aby odpowiedzieć na pytanie: czy metoda przybliżona może być stosowana do wyznaczania charakterystyk układów mechatronicznych. Analizę widmowo-modalną przeprowadzano w przypadku drgającej giętnie belki wysięgnikowej. Następnie model belki odwzorowano w pięciowierzchołkowy hipergraf, który to model, w wyniku zastosowania przybliżonej metody analizy widmowo - modalnej, można przedstawić w postaci hipergrafu trójwierzchołkowego. Takie ujęcie może stanowić wprowadzenie do syntezy drgających giętnie złożonych układów belkowych o odcinkowo stałym przekroju.
Źródło:
Archive of Mechanical Engineering; 2010, LVII, 4; 431-442
0004-0738
Pojawia się w:
Archive of Mechanical Engineering
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Generalized Hypergraph Coloring
Autorzy:
Schweser, Thomas
Powiązania:
https://bibliotekanauki.pl/articles/32083810.pdf
Data publikacji:
2021-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
hypergraph decomposition
vertex partition
degeneracy
coloring of hypergraphs
hypergraph properties
Opis:
A smooth hypergraph property \(\mathcal{P}\) is a class of hypergraphs that is hereditary and non-trivial, i.e., closed under induced subhypergraphs and it contains a non-empty hypergraph but not all hypergraphs. In this paper we examine \(\mathcal{P}\)-colorings of hypergraphs with smooth hypergraph properties \(\mathcal{P}\). A \(\mathcal{P}\)-coloring of a hypergraph $H$ with color set $C$ is a function $\varphi : V(H) → C$ such that \(H\big[\varphi^{−1}(c)\big]\) belongs to \(\mathcal{P}\) for all $c ∈ C$. Let $L : V (H) → 2^C$ be a so called list-assignment of the hypergraph $H$. Then, a (\(\mathcal{P}, L\))-coloring of $H$ is a \(\mathcal{P}\)-coloring $\varphi$ of $H$ such that $\varphi(v) ∈ L(v)$ for all $v ∈ V (H)$. The aim of this paper is a characterization of (\(\mathcal{P}, L\))-critical hypergraphs. Those are hypergraphs $H$ such that $H − v$ is (\(\mathcal{P}, L\))-colorable for all $v ∈ V (H)$ but $H$ itself is not. Our main theorem is a Gallai-type result for critical hypergraphs, which implies a Brooks-type result for (\(\mathcal{P}, L\))-colorable hypergraphs. In the last section, we prove a Gallai-type bound for the degree sum of (\(\mathcal{P}, L\))-critical locally simple hypergraphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2021, 41, 1; 103-121
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
A Characterization of Hypergraphs with Large Domination Number
Autorzy:
Henning, Michael A.
Löwenstein, Christian
Powiązania:
https://bibliotekanauki.pl/articles/31340924.pdf
Data publikacji:
2016-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
transversal
hypergraph
Opis:
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 \subseteq V $ such that for every vertex $ v \in V \ \backslash \ D $ there exists an edge $ \mathcal{e} \in E $ for which $ v \in \mathcal{e} $ and $ \mathcal{e} \cap D \ne \emptyset $. The domination number $ \gamma (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 \ge 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 $ \gamma (H) \ge (n + \floor{ (k − 3)//2 } m) // ( \floor{ 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.
Źródło:
Discussiones Mathematicae Graph Theory; 2016, 36, 2; 427-438
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Zastosowanie teorii hipergrafów w procesie analizy systemów dyskretnych opisanych sieciami Petriego
Application of hypergraphs to analysis of discrete-systems described with Petri Nets
Autorzy:
Adamski, M.
Wiśniewska, M.
Powiązania:
https://bibliotekanauki.pl/articles/155263.pdf
Data publikacji:
2011
Wydawca:
Stowarzyszenie Inżynierów i Techników Mechaników Polskich
Tematy:
hipergraf
transwersala dokładna
sieć Petriego
system dyskretny
hypergraph
exact transversal
Petri net
discrete system
Opis:
W artykule zaprezentowane zostały nowe metody wspomagające proces analizy systemów dyskretnych opisanych sieciami Petriego. Relacje w prototypowanym systemie dyskretnym są odwzorowane hiper-grafem. Dzięki temu projektowany, wbudowany, rekonfigurowany sterownik logiczny może zostać poddany efektywniejszemu procesowi analizy z wykorzystaniem nowych algorytmów, związanych z traktowanymi łącznie teoriami hipergrafów i sieci Petriego. Wykorzystano między innymi takie procedury jak dopełnienie, dualizm, transwersale, transwersale dokładne oraz kolorowanie hipergrafu. W artykule w sposób nieformalny wykorzystano autorskie twierdzenia, wspomagające cały proces projektowania sterowników. Szczególną uwagę zwrócono na nowe sposoby analizy systemów dyskretnych, opisanych sieciami Petriego, takie jak częściowa weryfikacja poprawności specyfikacji sterownika na podstawie struktury hipergrafu współbieżności oraz zastosowanie transwersal do-kładnych w procesie wyodrębniania powiązanych ze sobą procesów sekwencyjnych.
In the paper application of the hypergraph theory to analysis of discrete-systems described by means of Petri Nets is proposed. The relations between local states are represented by hypergraph vertices whose edges correspond to the global states. Therefore, the analysis of a prototype system can be performed by more effective operations supported by the hypergraph theory as well as the Petri net theory (such as dualism, hypergraph complement, transversals, exact transversals, hypergraph colouring). In the paper the authors propose application of the concurrency hypergraph to the analysis of a discrete-system. Such a structure refers to the traditional concurrency graph, however it keeps information about global states of the analysed system. Moreover, the concurrency hypergraph has some unique properties, which can lead to reduction in the computational complexity of some algorithms of the analysis. All minimal transversals in the concurrency hypergraph are also exact transversals. Therefore, such a hypergraph can be applied also to the decomposition process of a discrete-system, which is described by a Petri Net. After the analysis, a controller described by a Petri Net can be decomposed into concurrent sub-nets (concurrent automata). Each exact transversal of the concurrency hypergraph refers to the concurrent automata. The proposed solution allows significantly reducing the computational complexity to a polynomial. The traditional methods, based on the coloring of a concurrency graph are exponential time algorithms, thus they are defined to be NP-complete.
Źródło:
Pomiary Automatyka Kontrola; 2011, R. 57, nr 8, 8; 945-947
0032-4140
Pojawia się w:
Pomiary Automatyka Kontrola
Dostawca treści:
Biblioteka Nauki
Artykuł
Wyświetlanie 1-50 z 68

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