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ę "critical graphs" wg kryterium: Temat

  Lista filtrów
Wyrównaj
    Wyświetlanie 1-8 z 8
    Tytuł:
    Eternal Domination: Criticality and Reachability
    Autorzy:
    Klostermeyer, William F.
    MacGillivray, Gary
    Powiązania:
    https://bibliotekanauki.pl/articles/31342174.pdf
    Data publikacji:
    2017-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    dominating set
    eternal dominating set
    critical graphs
    Opis:
    We show that for every minimum eternal dominating set, D, of a graph G and every vertex v ∈ D, there is a sequence of attacks at the vertices of G which can be defended in such a way that an eternal dominating set not containing v is reached. The study of the stronger assertion that such a set can be reached after a single attack is defended leads to the study of graphs which are critical in the sense that deleting any vertex reduces the eternal domination number. Examples of these graphs and tight bounds on connectivity, edge-connectivity and diameter are given. It is also shown that there exist graphs in which deletion of any edge increases the eternal domination number, and graphs in which addition of any edge decreases the eternal domination number.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2017, 37, 1; 63-77
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Domination Game Critical Graphs
    Autorzy:
    Bujtás, Csilla
    Klavžar, Sandi
    Košmrlj, Gašper
    Powiązania:
    https://bibliotekanauki.pl/articles/31234048.pdf
    Data publikacji:
    2015-11-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    domination number
    domination game
    domination game critical graphs
    powers of cycles
    trees
    Opis:
    The domination game is played on a graph $G$ by two players who alternately take turns by choosing a vertex such that in each turn at least one previously undominated vertex is dominated. The game is over when each vertex becomes dominated. One of the players, namely Dominator, wants to finish the game as soon as possible, while the other one wants to delay the end. The number of turns when Dominator starts the game on $G$ and both players play optimally is the graph invariant $ \gamma_g (G) $, named the game domination number. Here we study the $ \gamma_g$-critical graphs which are critical with respect to vertex predomination. Besides proving some general properties, we characterize $ \gamma_g$-critical graphs with $ \gamma_g = 2$ and with $ \gamma_g = 3$, moreover for each n we identify the (infinite) class of all $\gamma_g$-critical ones among the $n$th powers $ C_N^n$ of cycles. Along the way we determine $\gamma_{g} ( C_N^n ) $ for all $n$ and $N$. Results of a computer search for $ \gamma_g$-critical trees are presented and several problems and research directions are also listed.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2015, 35, 4; 781-796
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On b-vertex and b-edge critical graphs
    Autorzy:
    Eschouf, N. I.
    Blidia, M.
    Powiązania:
    https://bibliotekanauki.pl/articles/952798.pdf
    Data publikacji:
    2015
    Wydawca:
    Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
    Tematy:
    b-coloring
    b-chromatic number
    critical graphs
    Opis:
    A b-coloring is a coloring of the vertices of a graph such that each color class contains a vertex that has a neighbor in all other color classes, and the b-chromatic number b(G) of a graph G is the largest integer k such that G admits a b-coloring with k colors. A simple graph G is called b+-vertex (edge) critical if the removal of any vertex (edge) of G increases its b-chromatic number. In this note, we explain some properties in b+-vertex (edge) critical graphs, and we conclude with two open problems.
    Źródło:
    Opuscula Mathematica; 2015, 35, 2; 171-180
    1232-9274
    2300-6919
    Pojawia się w:
    Opuscula Mathematica
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On the independence number of edge chromatic critical graphs
    Autorzy:
    Pang, Shiyou
    Miao, Lianying
    Song, Wenyao
    Miao, Zhengke
    Powiązania:
    https://bibliotekanauki.pl/articles/30148675.pdf
    Data publikacji:
    2014-08-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    edge coloring
    edge-chromatic critical graphs
    independence number
    Opis:
    In 1968, Vizing conjectured that for any edge chromatic critical graph $G = (V,E)$ with maximum degree $△$ and independence number $α(G)$, $α(G) ≤ \frac{|V|}{2}$. It is known that $α(G) < \frac{3∆−2}{5∆−2}|V|$. In this paper we improve this bound when $△≥4$. Our precise result depends on the number $n_2$ of 2-vertices in $G$, but in particular we prove that $α(G) ≤\frac{3∆−3}{5∆−3}|V|$ when $△≥5$ and $n_2≤2(△− 1)$.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2014, 34, 3; 577-584
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On vertex b-critical trees
    Autorzy:
    Blidia, M.
    Eschouf, N. I.
    Maffray, F.
    Powiązania:
    https://bibliotekanauki.pl/articles/254799.pdf
    Data publikacji:
    2013
    Wydawca:
    Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
    Tematy:
    b-coloring
    b-critical graphs
    b-critical trees
    Opis:
    A b-coloring is a proper coloring of the vertices of a graph such that each color class has a vertex that has neighbors of all other colors. The b-chromatic number of a graph G is the largest k such that G admits a b-coloring with k colors. A graph G is b-critical if the removal of any vertex of G decreases the b-chromatic number. We prove various properties of b-critical trees. In particular, we characterize b-critical trees.
    Źródło:
    Opuscula Mathematica; 2013, 33, 1; 19-28
    1232-9274
    2300-6919
    Pojawia się w:
    Opuscula Mathematica
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Double domination critical and stable graphs upon vertex removal
    Autorzy:
    Khelifi, Soufiane
    Chellali, Mustapha
    Powiązania:
    https://bibliotekanauki.pl/articles/743276.pdf
    Data publikacji:
    2012
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    double domination
    vertex removal critical graphs
    vertex removal stable graphs
    Opis:
    In a graph a vertex is said to dominate itself and all its neighbors. A double dominating set of a graph G is a subset of vertices that dominates every vertex of G at least twice. The double domination number of G, denoted $γ_{×2}(G)$, is the minimum cardinality among all double dominating sets of G. We consider the effects of vertex removal on the double domination number of a graph. A graph G is $γ_{×2}$-vertex critical graph ($γ_{×2}$-vertex stable graph, respectively) if the removal of any vertex different from a support vertex decreases (does not change, respectively) $γ_{×2}$(G). In this paper we investigate various properties of these graphs. Moreover, we characterize $γ_{×2}$-vertex critical trees and $γ_{×2}$-vertex stable trees.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2012, 32, 4; 643-657
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Weakly connected domination critical graphs
    Autorzy:
    Lemańska, M.
    Patyk, A.
    Powiązania:
    https://bibliotekanauki.pl/articles/255051.pdf
    Data publikacji:
    2008
    Wydawca:
    Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
    Tematy:
    weakly connected domination number
    tree
    critical graphs
    Opis:
    A dominating set D ⊂ V(G) is a weakly connected dominating set in G if the subgraph G[D]w = (NG[D], Ew) weakly induced by D is connected, where Ew is the set of all edges with at least one vertex in D. The weakly connected domination number ϒw(G) of a graph G is the minimum cardinality among all weakly connected dominating sets in G. The graph is said to be weakly connected domination critical (ϒw-critical) if for each u, v ∈ V(G) with v not adjacent to u, ϒw(G + vu) < ϒw(G). Further, G is k- ϒw-critical if ϒw(G) = k and for each edge e ∉ E(G), ϒw(G + e) < k. In this paper we consider weakly connected domination critical graphs and give some properties of 3-ϒw,-critical graphs.
    Źródło:
    Opuscula Mathematica; 2008, 28, 3; 325-330
    1232-9274
    2300-6919
    Pojawia się w:
    Opuscula Mathematica
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Gallais innequality for critical graphs of reducible hereditary properties
    Autorzy:
    Mihók, Peter
    Skrekovski, Riste
    Powiązania:
    https://bibliotekanauki.pl/articles/743466.pdf
    Data publikacji:
    2001
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    additive induced-hereditary property of graphs
    reducible property of graphs
    critical graph
    Gallai's Theorem
    Opis:
    In this paper Gallai's inequality on the number of edges in critical graphs is generalized for reducible additive induced-hereditary properties of graphs in the following way. Let $₁,₂,...,ₖ$ (k ≥ 2) be additive induced-hereditary properties, $ = ₁ ∘ ₂ ∘ ... ∘ₖ$ and $δ = ∑_{i=1}^k δ(_i)$. Suppose that G is an -critical graph with n vertices and m edges. Then 2m ≥ δn + (δ-2)/(δ²+2δ-2)*n + (2δ)/(δ²+2δ-2) unless = ² or $G = K_{δ+1}$. The generalization of Gallai's inequality for -choice critical graphs is also presented.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2001, 21, 2; 167-177
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
      Wyświetlanie 1-8 z 8

      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