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

  Lista filtrów
Wyrównaj
Wyświetlanie 1-15 z 23
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ł:
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ł:
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ł:
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ł:
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ł:
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ł:
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ł:
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 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ł:
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ł:
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ł:
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ł:
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ł:
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ł
Wyświetlanie 1-15 z 23

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