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ę "Nordhaus-Gaddum" wg kryterium: Temat

  Lista filtrów
Wyrównaj
    Wyświetlanie 1-4 z 4
    Tytuł:
    Generalised irredundance in graphs: Nordhaus-Gaddum bounds
    Autorzy:
    Cockayne, Ernest
    Finbow, Stephen
    Powiązania:
    https://bibliotekanauki.pl/articles/744461.pdf
    Data publikacji:
    2004
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    graph
    generalised irredundance
    Nordhaus-Gaddum
    Opis:
    For each vertex s of the vertex subset S of a simple graph G, we define Boolean variables p = p(s,S), q = q(s,S) and r = r(s,S) which measure existence of three kinds of S-private neighbours (S-pns) of s. A 3-variable Boolean function f = f(p,q,r) may be considered as a compound existence property of S-pns. The subset S is called an f-set of G if f = 1 for all s ∈ S and the class of f-sets of G is denoted by $Ω_f(G)$. Only 64 Boolean functions f can produce different classes $Ω_f(G)$, special cases of which include the independent sets, irredundant sets, open irredundant sets and CO-irredundant sets of G. Let $Q_f(G)$ be the maximum cardinality of an f-set of G. For each of the 64 functions f, we establish sharp upper bounds for the sum $Q_f(G) + Q_f(G̅)$ and the product $Q_f(G)Q_f(G̅)$ in terms of n, the order of G.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2004, 24, 1; 147-160
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    A Note on Roman Domination of Digraphs
    Autorzy:
    Chen, Xiaodan
    Hao, Guoliang
    Xie, Zhihong
    Powiązania:
    https://bibliotekanauki.pl/articles/31343785.pdf
    Data publikacji:
    2019-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    Roman domination number
    domination number
    digraph
    Nordhaus-Gaddum
    Opis:
    A vertex subset $S$ of a digraph $D$ is called a dominating set of $D$ if every vertex not in $S$ is adjacent from at least one vertex in $S$. The domination number of a digraph $D$, denoted by $ \gamma(D) $, is the minimum cardinality of a dominating set of $D$. A Roman dominating function (RDF) on a digraph $D$ is a function $ f : V (D) \rightarrow {0, 1, 2} $ satisfying the condition that every vertex $v$ with $f(v) = 0$ has an in-neighbor $u$ with $f(u) = 2$. The weight of an RDF $f$ is the value $ \omega (f) = \Sigma_{ v \in V(D) } f(v) $. The Roman domination number of a digraph $D$, denoted by $ \gamma_R (D) $, is the minimum weight of an RDF on $D$. In this paper, for any integer $k$ with $ 2 \le k \le \gamma(D) $, we characterize the digraphs $D$ of order $ n \ge 4 $ with $ \delta − (D) \ge 1 $ for which $ \gamma_R(D) = (D) + k $ holds. We also characterize the digraphs $D$ of order $ n \ge k $ with $ \gamma_R(D) = k $ for any positive integer $k$. In addition, we present a Nordhaus-Gaddum bound on the Roman domination number of digraphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2019, 39, 1; 13-21
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Various Bounds for Liar’s Domination Number
    Autorzy:
    Alimadadi, Abdollah
    Mojdeh, Doost Ali
    Rad, Nader Jafari
    Powiązania:
    https://bibliotekanauki.pl/articles/31340859.pdf
    Data publikacji:
    2016-08-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    liar’s domination
    diameter
    regular graph
    Nordhaus-Gaddum
    Opis:
    Let $ G = (V,E) $ be a graph. A set $ S \subseteq V $ is a dominating set if \( \bigcup_{v \in S} N[v] = V \), where $ N[v] $ is the closed neighborhood of $ v $. Let $ L \subseteq V $ be a dominating set, and let $v$ be a designated vertex in $V$ (an intruder vertex). Each vertex in $ L \cap N[v] $ can report that $v$ is the location of the intruder, but (at most) one $ x \in L \cap N[v] $ can report any $ w \in N[x] $ as the intruder location or $ x $ can indicate that there is no intruder in $ N[x] $. A dominating set $L$ is called a liar’s dominating set if every $ v \in V (G) $ can be correctly identified as an intruder location under these restrictions. The minimum cardinality of a liar’s dominating set is called the liar’s domination number, and is denoted by $ \gamma_{LR} (G) $. In this paper, we present sharp bounds for the liar’s domination number in terms of the diameter, the girth and clique covering number of a graph. We present two Nordhaus-Gaddum type relations for $ \gamma_{LR} (G) $, and study liar’s dominating set sensitivity versus edge-connectivity. We also present various bounds for the liar’s domination component number, that is, the maximum number of components over all minimum liar’s dominating sets.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2016, 36, 3; 629-641
    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ł
      Wyświetlanie 1-4 z 4

      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