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ę "universal graph" wg kryterium: Temat

  Lista filtrów
Wyrównaj
    Wyświetlanie 1-5 z 5
    Tytuł:
    Universality in Graph Properties with Degree Restrictions
    Autorzy:
    Broere, Izak
    Heidema, Johannes
    Mihók, Peter
    Powiązania:
    https://bibliotekanauki.pl/articles/30146518.pdf
    Data publikacji:
    2013-07-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    countable graph
    universal graph
    induced-hereditary
    k-degenerate graph
    graph with colouring number at most k + 1
    graph property with assignment
    Opis:
    Rado constructed a (simple) denumerable graph R with the positive integers as vertex set with the following edges: For given m and n with m < n, m is adjacent to n if n has a 1 in the m’th position of its binary expansion. It is well known that R is a universal graph in the set ℐc of all countable graphs (since every graph in ℐc is isomorphic to an induced subgraph of R). A brief overview of known universality results for some induced-hereditary subsets of ℐc is provided. We then construct a k-degenerate graph which is universal for the induced-hereditary property of finite k-degenerate graphs. In order to attempt the corresponding problem for the property of countable graphs with colouring number at most k + 1, the notion of a property with assignment is introduced and studied. Using this notion, we are able to construct a universal graph in this graph property and investigate its attributes.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2013, 33, 3; 477-492
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Universality for and in Induced-Hereditary Graph Properties
    Autorzy:
    Broere, Izak
    Heidema, Johannes
    Powiązania:
    https://bibliotekanauki.pl/articles/30146860.pdf
    Data publikacji:
    2013-03-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    countable graph
    universal graph
    induced-hereditary property
    Opis:
    The well-known Rado graph $R$ is universal in the set of all countable graphs \( \mathcal{I} \), since every countable graph is an induced subgraph of $R$. We study universality in \( \mathcal{I} \) and, using $R$, show the existence of $2^{\aleph_0}$ pairwise non-isomorphic graphs which are universal in \( \mathcal{I} \) and denumerably many other universal graphs in \( \mathcal{I} \) with prescribed attributes. Then we contrast universality for and universality in induced-hereditary properties of graphs and show that the overwhelming majority of induced-hereditary properties contain no universal graphs. This is made precise by showing that there are $ 2^{2^{\aleph_0 } }$ properties in the lattice $ \mathbb{K}_\le $ of induced-hereditary properties of which only at most $ 2^{\aleph_0} $ contain universal graphs. In a final section we discuss the outlook on future work; in particular the question of characterizing those induced-hereditary properties for which there is a universal graph in the property.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2013, 33, 1; 33-47
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On universal graphs for hom-properties
    Autorzy:
    Mihók, Peter
    Miškuf, Jozef
    Semanišin, Gabriel
    Powiązania:
    https://bibliotekanauki.pl/articles/744408.pdf
    Data publikacji:
    2009
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    universal graph
    weakly universal graph
    hom-property
    core
    Opis:
    A graph property is any isomorphism closed class of simple graphs. For a simple finite graph H, let → H denote the class of all simple countable graphs that admit homomorphisms to H, such classes of graphs are called hom-properties. Given a graph property , a graph G ∈ is universal in if each member of is isomorphic to an induced subgraph of G. In particular, we consider universal graphs in → H and we give a new proof of the existence of a universal graph in → H, for any finite graph H.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2009, 29, 2; 401-409
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On the hat problem on a graph
    Autorzy:
    Krzywkowski, M.
    Powiązania:
    https://bibliotekanauki.pl/articles/256048.pdf
    Data publikacji:
    2012
    Wydawca:
    Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
    Tematy:
    hat problem
    graph
    degree
    neighborhood
    neighborhood-dominated
    unicyclic
    universal vertex
    Nordhaus-Gaddum
    Opis:
    The topic of this paper is the hat problem in which each of n players is uniformly and independently fitted with a blue or red hat. Then everybody can try to guess simultaneously his own hat color by looking at the hat colors of the other players. The team wins if at least one player guesses his hat color correctly, and no one guesses his hat color wrong; otherwise the team loses. The aim is to maximize the probability of winning. In this version every player can see everybody excluding himself. We consider such a problem on a graph, where vertices correspond to players, and a player can see each player to whom he is connected by an edge. The solution of the hat problem on a graph is known for trees and for cycles on four or at least nine vertices. In this paper first we give an upper bound on the maximum chance of success for graphs with neighborhood-dominated vertices. Next we solve the problem on unicyclic graphs containing a cycle on at least nine vertices. We prove that the maximum chance of success is one by two. Then we consider the hat problem on a graph with a universal vertex. We prove that there always exists an optimal strategy such that in every case some vertex guesses its color. Moreover, we prove that there exists a graph with a universal vertex for which there exists an optimal strategy such that in some case no vertex guesses its color. We also give some Nordhaus-Gaddum type inequalities.
    Źródło:
    Opuscula Mathematica; 2012, 32, 2; 285-296
    1232-9274
    2300-6919
    Pojawia się w:
    Opuscula Mathematica
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On infinite uniquely partitionable graphs and graph properties of finite character
    Autorzy:
    Bucko, Jozef
    Mihók, Peter
    Powiązania:
    https://bibliotekanauki.pl/articles/743160.pdf
    Data publikacji:
    2009
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    graph property of finite character
    reducibility
    uniquely partitionable graphs
    weakly universal graph
    Opis:
    A graph property is any nonempty isomorphism-closed class of simple (finite or infinite) graphs. A graph property is of finite character if a graph G has a property if and only if every finite induced subgraph of G has a property . Let ₁,₂,...,ₙ be graph properties of finite character, a graph G is said to be (uniquely) (₁, ₂, ...,ₙ)-partitionable if there is an (exactly one) partition {V₁, V₂, ..., Vₙ} of V(G) such that $G[V_i] ∈ _i$ for i = 1,2,...,n. Let us denote by ℜ = ₁ ∘ ₂ ∘ ... ∘ ₙ the class of all (₁,₂,...,ₙ)-partitionable graphs. A property ℜ = ₁ ∘ ₂ ∘ ... ∘ ₙ, n ≥ 2 is said to be reducible. We prove that any reducible additive graph property ℜ of finite character has a uniquely (₁, ₂, ...,ₙ)-partitionable countable generating graph. We also prove that for a reducible additive hereditary graph property ℜ of finite character there exists a weakly universal countable graph if and only if each property $_i$ has a weakly universal graph.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2009, 29, 2; 241-251
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
      Wyświetlanie 1-5 z 5

      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