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-23 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ł
    Tytuł:
    \( \mathcal{P} \)-Apex Graphs
    Autorzy:
    Borowiecki, Mieczysław
    Drgas-Burchardt, Ewa
    Sidorowicz, Elżbieta
    Powiązania:
    https://bibliotekanauki.pl/articles/31342421.pdf
    Data publikacji:
    2018-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    induced hereditary classes of graphs
    forbidden subgraphs
    hypergraphs
    transversal number
    Opis:
    Let \( \mathcal{P} \) be an arbitrary class of graphs that is closed under taking induced subgraphs and let \( \mathcal{C}( \mathcal{P} ) \) be the family of forbidden subgraphs for \( \mathcal{P} \). We investigate the class \( \mathcal{P} (k) \) consisting of all the graphs \( G \) for which the removal of no more than \( k \) vertices results in graphs that belong to \( \mathcal{P} \). This approach provides an analogy to apex graphs and apex-outerplanar graphs studied previously. We give a sharp upper bound on the number of vertices of graphs in \( \mathcal{C}( \mathcal{P}(1)) \) and we give a construction of graphs in \( \mathcal{C}( \mathcal{P}(k)) \) of relatively large order for \( k \ge 2 \). This construction implies a lower bound on the maximum order of graphs in \( \mathcal{C}( \mathcal{P}(k)) \). Especially, we investigate \( \mathcal{C}( \mathcal{W}_r(1)) \), where \( \mathcal{W}_r \) denotes the class of \( \mathcal{P}_r \)-free graphs. We determine some forbidden subgraphs for the class \( \mathcal{W}_r(1) \) with the minimum and maximum number of vertices. Moreover, we give sufficient conditions for graphs belonging to \( \mathcal{C} ( \mathcal{P} (k)) \), where \( \mathcal{P} \) is an additive class, and a characterisation of all forests in \( \mathcal{C} ( \mathcal{P} (k)) \). Particularly we deal with \( \mathcal{C} ( \mathcal{P} (1)) \), where \( \mathcal{P} \) is a class closed under substitution and obtain a characterisation of all graphs in the corresponding \( \mathcal{C} ( \mathcal{P} (1)) \). In order to obtain desired results we exploit some hypergraph tools and this technique gives a new result in the hypergraph theory.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2018, 38, 2; 323-349
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    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ł:
    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ł:
    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ł:
    The theorems of Koenig and Birkhoff and their connection with the minimization of the duration time of the measurements of automatic telecommunication channels
    Autorzy:
    Perz, Szczepan
    Zaremba, Leszek
    Powiązania:
    https://bibliotekanauki.pl/articles/748569.pdf
    Data publikacji:
    1982
    Wydawca:
    Polskie Towarzystwo Matematyczne
    Tematy:
    Channel models (including quantum), Discrete-time control systems, Hypergraphs, Matrix equations and identities, Matrices of integers, Stochastic matrices
    Opis:
    .
    A problem (P) of minimization of the duration time of the measurements of automatic telecommunication channels is considered. P is a discrete optimization problem solved by graph theory methods. It is defined by (i)-(v), where: (i) for each i, 1≤i≤p, and j, 1≤1≤p, there are given k ij channels to be measured between node ”i” and node ”j”; (ii) measurement of one channel lasts one unit; (iii) there are exactly two devices, say A, B, in each node (the case where there is an arbitrary number of devices A, B in each node may be easily reduced to this case); (iv) the channel between node ”i” and node ”j” may be measured only by use of device A being present in node ”i” and device B in node ”j”; (v) in each time both devices A or B may measure only one channel. To solve P, some knowledge of hypergraphs as well as functional analysis (the Krein-Milman theorem) and linear algebra (the Koenig theorem) is necessary. The Koenig theorem is proved in a simple manner similarly as the dual Koenig theorem (which is a new result). As corollaries the Birkhoff theorem about bistochastic matrices and the dual Birkhoff theorem are deduced.
    Źródło:
    Mathematica Applicanda; 1982, 10, 19
    1730-2668
    2299-4009
    Pojawia się w:
    Mathematica Applicanda
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Autorski system wspomagający proces dekompozycji sieci Petriego na podsieci typu automatowego
    CAD system for automatic decomposition of Petri Nets
    Autorzy:
    Wiśniewska, M.
    Powiązania:
    https://bibliotekanauki.pl/articles/155267.pdf
    Data publikacji:
    2011
    Wydawca:
    Stowarzyszenie Inżynierów i Techników Mechaników Polskich
    Tematy:
    hipergraf
    transwersala dokładna
    system Hippo wspomagający proces dekompozycji sieci Petriego
    hypergraph
    hypergraph transversal
    CAD system Hippo for automatic decomposition of Petri Nets based on hypergraphs
    Opis:
    W referacie przedstawiono autorski system komputerowy wspomagający proces dekompozycji sieci Petriego na podsieci typu automatowego. System sterujący zostaje opisany za pomocą sieci Petriego, na podstawie której określany jest graf lub hipergraf współbieżności. Macierz incydencji hipergrafu współbieżności stanowi dane wejściowe systemu Hippo. Aplikacja oferuje przeprowadzenie dekompozycji z zastosowaniem operacji bazujących na teorii hipergrafów różnymi metodami i umożliwia wybór najlepszej z nich.
    The dedicated CAD system Hippo for automatic decomposition of Petri Nets into concurrent automata is presented. At the beginning the reachability graph is calculated for the Petri Net which may be easily represented by a concurrency graph or a hypergraph. Such structures are input for main decomposition process. There are several methods for decomposition of Petri Nets. The most popular one is based on the colouring of the concurrency graph, however recently, a few new algorithms based on hypergraph theory have appeared. Contrary to a concurrency graph, application of a concurrency hypergraph to the decomposition of Petri Net enables using new and fast methods. The solution can be found by colouring of a concurrency hypergraph, calculating its complement or finding exact transversals. Especially, the last method is most interesting, because it allows reducing the computational complexity to a polynomial. In the paper the decomposition process is presented in detail. There are several ways of decomposition presented (based on colouring graphs/hypergraphs), calculating hypergraph complement or finding its exact transversals. Each of the presented method was implemented in Hippo. The decomposition process is automated. As the input of the Hippo system, a description of a concurrency graph or hypergraph is required. Based on this structure and a selected decomposition method, Hippo finds and prints results. The obtained results are presented in graphical and text form.
    Źródło:
    Pomiary Automatyka Kontrola; 2011, R. 57, nr 8, 8; 948-950
    0032-4140
    Pojawia się w:
    Pomiary Automatyka Kontrola
    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ł:
    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ł
      Wyświetlanie 1-23 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