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ę "k-domination" wg kryterium: Temat

  Lista filtrów
Wyrównaj
    Wyświetlanie 1-31 z 31
    Tytuł:
    On the Total k-Domination in Graphs
    Autorzy:
    Bermudo, Sergio
    Hernández-Gómez, Juan C.
    Sigarreta, José M.
    Powiązania:
    https://bibliotekanauki.pl/articles/31342422.pdf
    Data publikacji:
    2018-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    k -domination
    total k -domination
    k -tuple domination
    k -tuple total domination
    Opis:
    Let G=(V, E) be a graph; a set S ⊆ V is a total k-dominating set if every vertex v ∈ V has at least k neighbors in S. The total k-domination number γkt(G) is the minimum cardinality among all total k-dominating sets. In this paper we obtain several tight bounds for the total k-domination number of a graph. In particular, we investigate the relationship between the total k-domination number of a graph and the order, the size, the girth, the minimum and maximum degree, the diameter, and other domination parameters of the graph.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2018, 38, 1; 301-317
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Bounds on perfect k-domination in trees: an algorithmic approach
    Autorzy:
    Chaluvaraju, B.
    Vidya, K. A.
    Powiązania:
    https://bibliotekanauki.pl/articles/255985.pdf
    Data publikacji:
    2012
    Wydawca:
    Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
    Tematy:
    k-domination
    perfect domination
    perfect k-domination
    Opis:
    Let k be a positive integer and G = (V, E) be a graph. A vertex subset D of a graph G is called a perfect k-dominating set of G if every vertex v of G not in D is adjacent to exactly k vertices of D. The minimum cardinality of a perfect k -dominating set of G is the perfect k-domination number γkp (G ). In this paper, a sharp bound for γkp (T) is obtained where T is a tree.
    Źródło:
    Opuscula Mathematica; 2012, 32, 4; 707-714
    1232-9274
    2300-6919
    Pojawia się w:
    Opuscula Mathematica
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On the total k-domination number of graphs
    Autorzy:
    Kazemi, Adel
    Powiązania:
    https://bibliotekanauki.pl/articles/743228.pdf
    Data publikacji:
    2012
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    total k-domination (k-tuple total domination) number
    k-tuple domination number
    k-transversal number
    Opis:
    Let k be a positive integer and let G = (V,E) be a simple graph. The k-tuple domination number $γ_{×k}(G)$ of G is the minimum cardinality of a k-tuple dominating set S, a set that for every vertex v ∈ V, $|N_G[v] ∩ S| ≥ k$. Also the total k-domination number $γ_{×k,t}(G)$ of G is the minimum cardinality of a total k -dominating set S, a set that for every vertex v ∈ V, $|N_G(v) ∩ S| ≥ k$. The k-transversal number τₖ(H) of a hypergraph H is the minimum size of a subset S ⊆ V(H) such that |S ∩e | ≥ k for every edge e ∈ E(H).
    We know that for any graph G of order n with minimum degree at least k, $γ_{×k}(G) ≤ γ_{×k,t}(G) ≤ n$. Obviously for every k-regular graph, the upper bound n is sharp. Here, we give a sufficient condition for $γ_{×k,t}(G) < n$. Then we characterize complete multipartite graphs G with $γ_{×k}(G) = γ_{×k,t}(G)$. We also state that the total k-domination number of a graph is the k -transversal number of its open neighborhood hypergraph, and also the domination number of a graph is the transversal number of its closed neighborhood hypergraph. Finally, we give an upper bound for the total k -domination number of the cross product graph G×H of two graphs G and H in terms on the similar numbers of G and H. Also, we show that this upper bound is strict for some graphs, when k = 1.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2012, 32, 3; 419-426
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Fractional distance domination in graphs
    Autorzy:
    Arumugam, S.
    Mathew, Varughese
    Karuppasamy, K.
    Powiązania:
    https://bibliotekanauki.pl/articles/743206.pdf
    Data publikacji:
    2012
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    domination
    distance k-domination
    distance k-dominating function
    k-packing
    fractional distance k-domination
    Opis:
    Let G = (V,E) be a connected graph and let k be a positive integer with k ≤ rad(G). A subset D ⊆ V is called a distance k-dominating set of G if for every v ∈ V - D, there exists a vertex u ∈ D such that d(u,v) ≤ k. In this paper we study the fractional version of distance k-domination and related parameters.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2012, 32, 3; 449-459
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    The Slater and Sub-k-Domination Number of a Graph with Applications to Domination and k-Domination
    Autorzy:
    Amos, David
    Asplund, John
    Brimkov, Boris
    Davila, Randy
    Powiązania:
    https://bibliotekanauki.pl/articles/32083827.pdf
    Data publikacji:
    2020-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    Slater number
    domination number
    sub- k -domination number
    k -domination number
    degree sequence index strategy
    Opis:
    In this paper we introduce and study a new graph invariant derived from the degree sequence of a graph G, called the sub-k-domination number and denoted subk(G). This invariant serves as a generalization of the Slater number; in particular, we show that subk(G) is a computationally efficient sharp lower bound on the k-domination number of G, and improves on several known lower bounds. We also characterize the sub-k-domination numbers of several families of graphs, provide structural results on sub-k-domination, and explore properties of graphs which are subk(G)-critical with respect to addition and deletion of vertices and edges.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2020, 40, 1; 209-225
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    A note on bipartite graphs whose [1, k]-domination number equal to their number of vertices
    Autorzy:
    Ghareghani, Narges
    Peterin, Iztok
    Sharifani, Pouyeh
    Powiązania:
    https://bibliotekanauki.pl/articles/256007.pdf
    Data publikacji:
    2020
    Wydawca:
    Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
    Tematy:
    domination
    [1, k]-domination number
    [l,k]-total domination number
    bipartite graphs
    Opis:
    A subset D of the vertex set V of a graph G is called an [1, k]-dominating set if every vertex from V — D is adjacent to at least one vertex and at most fc vertices of D. A [1, k]-dominating set with the minimum number of vertices is called a [formula]-set and the number of its vertices is the [1, k]-domination number [formula] of G. In this short note we show that the decision problem whether [formula] is an NP-hard problem, even for bipartite graphs. Also, a simple construction of a bipartite graph G of order n satisfying [formula] is given for every integer n ≥ (k + l)(2k + 3).
    Źródło:
    Opuscula Mathematica; 2020, 40, 3; 375-382
    1232-9274
    2300-6919
    Pojawia się w:
    Opuscula Mathematica
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    A note on k-Roman graphs
    Autorzy:
    Bouchou, A.
    Blidia, M.
    Chellali, M.
    Powiązania:
    https://bibliotekanauki.pl/articles/255821.pdf
    Data publikacji:
    2013
    Wydawca:
    Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
    Tematy:
    Roman k-domination
    k-Roman graph
    Opis:
    Let G = (V,E) be a graph and let k be a positive integer. A subset D of V (G) is a k-dominating set of G if every vertex in V (G) \D has at least k neighbours in D. The k-domination number Υk(G) is the minimum cardinality of a k-dominating set of G. A Roman k-dominating function on G is a function f : V (G) →{0, 1, 2} such that every vertex u for which f(u) = 0 is adjacent to at least k vertices v1, v2, . . . , vk with f(vi) = 2 for i = 1, 2, . . . , k. The weight of a Roman k-dominating function is the value [formula] and the minimum weight of a Roman k-dominating function on G is called the Roman k-domination number Υk(G) of G. A graph G is said to be a k-Roman graph if ΥkR(G) = 2Υk(G) . In this note we study k-Roman graphs.
    Źródło:
    Opuscula Mathematica; 2013, 33, 4; 641-646
    1232-9274
    2300-6919
    Pojawia się w:
    Opuscula Mathematica
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Trees with equal global offensive k-alliance and k-domination numbers
    Autorzy:
    Chellali, M.
    Powiązania:
    https://bibliotekanauki.pl/articles/255451.pdf
    Data publikacji:
    2010
    Wydawca:
    Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
    Tematy:
    global offensive k-alliance number
    k-domination number
    trees
    Opis:
    Let k ≥ 1 be an integer. A set S of vertices of a graph G = (V (G), E(G)) is called a global offensive k-alliance if |N(v) ∩ S| ≥ |N(v) - S| + k for every v ∈ V (G) - S, where N(v) is the neighborhood of v. The subset S is a k-dominating set of G if every vertex in V (G) - S has at least k neighbors in S. The global offensive k-alliance number [formula] is the minimum cardinality of a global offensive k-alliance in G and the k-domination number ϒ k(G) is the minimum cardinality of a k-dominating set of G. For every integer k ≥ 1 every graph G satisfies [formula]. In this paper we provide for k ≥ 2 a characterization of trees T with equal [formula] and ϒ k(T).
    Źródło:
    Opuscula Mathematica; 2010, 30, 3; 249-254
    1232-9274
    2300-6919
    Pojawia się w:
    Opuscula Mathematica
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Weak signed Roman k-domination in digraphs
    Autorzy:
    Volkmann, Lutz
    Powiązania:
    https://bibliotekanauki.pl/articles/29519480.pdf
    Data publikacji:
    2024
    Wydawca:
    Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
    Tematy:
    digraph
    weak signed Roman k-dominating function
    weak signed Roman k-domination number
    signed Roman k-dominating function
    signed Roman k-domination number
    Opis:
    Let $ k ≥ 1 $ be an integer, and let $ D $ be a finite and simple digraph with vertex set $ V (D) $. A weak signed Roman k-dominating function (WSRkDF) on a digraph $ D $ is a function $ f : V (D) → {−1, 1, 2} $ satisfying the condition that $ \Sigma_{x∈N^−[v]} f(x) ≥ k $ for each v ∈ V (D), where $ N^− [v] $ consists of $ v $ and all vertices of $ D $ from which arcs go into $ v $. The weight of a WSRkDF $ f $ is $ w(f) = \Sigma_{v∈V} (D) f(v) $. The weak signed Roman k-domination number $ \gamma_{wsR}^k (D) $ is the minimum weight of a WSRkDF on $ D $. In this paper we initiate the study of the weak signed Roman k-domination number of digraphs, and we present different bounds on $ \gamma_{wsR}^k (D) $. In addition, we determine the weak signed Roman k-domination number of some classes of digraphs. Some of our results are extensions of well-known properties of the weak signed Roman domination number $ \gamma_{wsR} (D) = \gamma_{wsR}^1 (D) $ and the signed Roman k-domination number $ \gamma_{sR}^k (D) $.
    Źródło:
    Opuscula Mathematica; 2024, 44, 2; 285-296
    1232-9274
    2300-6919
    Pojawia się w:
    Opuscula Mathematica
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Some Variations of Perfect Graphs
    Autorzy:
    Dettlaff, Magda
    Lemańska, Magdalena
    Semanišin, Gabriel
    Zuazua, Rita
    Powiązania:
    https://bibliotekanauki.pl/articles/31340821.pdf
    Data publikacji:
    2016-08-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    k-path vertex cover
    distance k-domination number
    perfect graphs
    Opis:
    We consider (ψk−γk−1)-perfect graphs, i.e., graphs G for which ψk(H) = γk−1(H) for any induced subgraph H of G, where ψk and γk−1 are the k-path vertex cover number and the distance (k − 1)-domination number, respectively. We study (ψk−γk−1)-perfect paths, cycles and complete graphs for k ≥ 2. Moreover, we provide a complete characterisation of (ψ2 − γ1)- perfect graphs describing the set of its forbidden induced subgraphs and providing the explicit characterisation of the structure of graphs belonging to this family.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2016, 36, 3; 661-668
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    The total {k}-domatic number of digraphs
    Autorzy:
    Sheikholeslami, Seyed
    Volkmann, Lutz
    Powiązania:
    https://bibliotekanauki.pl/articles/743233.pdf
    Data publikacji:
    2012
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    digraph
    total {k}-dominating function
    total {k}-domination number
    total {k}-domatic number
    Opis:
    For a positive integer k, a total {k}-dominating function of a digraph D is a function f from the vertex set V(D) to the set {0,1,2, ...,k} such that for any vertex v ∈ V(D), the condition $∑_{u ∈ N^{ -}(v)}f(u) ≥ k$ is fulfilled, where N¯(v) consists of all vertices of D from which arcs go into v. A set ${f₁,f₂, ...,f_d}$ of total {k}-dominating functions of D with the property that $∑_{i = 1}^d f_i(v) ≤ k$ for each v ∈ V(D), is called a total {k}-dominating family (of functions) on D. The maximum number of functions in a total {k}-dominating family on D is the total {k}-domatic number of D, denoted by $dₜ^{{k}}(D)$. Note that $dₜ^{{1}}(D)$ is the classic total domatic number $dₜ(D)$. In this paper we initiate the study of the total {k}-domatic number in digraphs, and we present some bounds for $dₜ^{{k}}(D)$. Some of our results are extensions of well-know properties of the total domatic number of digraphs and the total {k}-domatic number of graphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2012, 32, 3; 461-471
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Signed Roman Edge k -Domination in Graphs
    Autorzy:
    Asgharsharghi, Leila
    Sheikholeslami, Seyed Mahmoud
    Volkmann, Lutz
    Powiązania:
    https://bibliotekanauki.pl/articles/31342188.pdf
    Data publikacji:
    2017-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    signed Roman edge k -dominating function
    signed Roman edge k -domination number
    Opis:
    Let $ k \ge 1 $ be an integer, and $ G = (V, E) $ be a finite and simple graph. The closed neighborhood $ N_G [e]$ of an edge $e$ in a graph $G$ is the set consisting of $e$ and all edges having a common end-vertex with $e$. A signed Roman edge $k$-dominating function (SREkDF) on a graph $G$ is a function $ f : E \rightarrow {−1, 1, 2} $ satisfying the conditions that (i) for every edge $e$ of $G$, $ \Sigma_{ x \in N_G [e] } f(x) \ge k $ and (ii) every edge e for which $f(e) = −1$ is adjacent to at least one edge $ e^′ $ for which $ f(e^′) = 2 $. The minimum of the values $ \Sigma_{e \in E} f(e) $, taken over all signed Roman edge $k$-dominating functions $f$ of $G$ is called the signed Roman edge $k$-domination number of $G$, and is denoted by $ \gamma_{sRk}^' (G) $. In this paper we initiate the study of the signed Roman edge $k$-domination in graphs and present some (sharp) bounds for this parameter.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2017, 37, 1; 39-53
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Bounds on the Signed Roman k-Domination Number of a Digraph
    Autorzy:
    Chen, Xiaodan
    Hao, Guoliang
    Volkmann, Lutz
    Powiązania:
    https://bibliotekanauki.pl/articles/31343713.pdf
    Data publikacji:
    2019-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    signed Roman k-dominating function
    signed Roman k-domination number
    digraph
    oriented tree
    Opis:
    Let $k$ be a positive integer. A signed Roman $k$-dominating function (SRkDF) on a digraph $D$ is a function $ f : V (D) \rightarrow \{−1, 1, 2 \} $ satisfying the conditions that (i) $ \Sigma_{ x \in N^− [v] } f(x) \ge k $ for each $ v \in V (D) $, where $ N^− [v] $ is the closed in-neighborhood of $v$, and (ii) each vertex $u$ for which $f(u) = −1$ has an in-neighbor $v$ for which $f(v) = 2$. The weight of an SRkDF $f$ is $ \Sigma_{ v \in V (D) } f(v) $. The signed Roman $k$-domination number $ \gamma_{sR}^k (D) $ of a digraph $D$ is the minimum weight of an SRkDF on $D$. We determine the exact values of the signed Roman $k$-domination number of some special classes of digraphs and establish some bounds on the signed Roman $k$-domination number of general digraphs. In particular, for an oriented tree $T$ of order $n$, we show that $ \gamma_{sR}^2 (T) \ge (n + 3)//2 $, and we characterize the oriented trees achieving this lower bound.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2019, 39, 1; 67-79
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Total Domination in Generalized Prisms and a New Domination Invariant
    Autorzy:
    Tepeh, Aleksandra
    Powiązania:
    https://bibliotekanauki.pl/articles/32222717.pdf
    Data publikacji:
    2021-11-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    domination
    k -rainbow total domination
    total domination
    Opis:
    In this paper we complement recent studies on the total domination of prisms by considering generalized prisms, i.e., Cartesian products of an arbitrary graph and a complete graph. By introducing a new domination invariant on a graph G, called the k-rainbow total domination number and denoted by γkrt(G), it is shown that the problem of finding the total domination number of a generalized prism G □ Kk is equivalent to an optimization problem of assigning subsets of {1, 2, . . ., k} to vertices of G. Various properties of the new domination invariant are presented, including, inter alia, that γkrt(G) = n for a nontrivial graph G of order n as soon as k ≥ 2Δ(G). To prove the mentioned result as well as the closed formulas for the k-rainbow total domination number of paths and cycles for every k, a new weight-redistribution method is introduced, which serves as an efficient tool for establishing a lower bound for a domination invariant.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2021, 41, 4; 1165-1178
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Some results on total domination in direct products of graphs
    Autorzy:
    Dorbec, Paul
    Gravier, Sylvain
    Klavžar, Sandi
    Spacapan, Simon
    Powiązania:
    https://bibliotekanauki.pl/articles/743885.pdf
    Data publikacji:
    2006
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    direct product
    total domination
    k-tuple domination
    open packing
    domination
    Opis:
    Upper and lower bounds on the total domination number of the direct product of graphs are given. The bounds involve the {2}-total domination number, the total 2-tuple domination number, and the open packing number of the factors. Using these relationships one exact total domination number is obtained. An infinite family of graphs is constructed showing that the bounds are best possible. The domination number of direct products of graphs is also bounded from below.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2006, 26, 1; 103-112
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Upper Bounds on the Signed Total (k, k)-Domatic Number of Graphs
    Autorzy:
    Volkmann, Lutz
    Powiązania:
    https://bibliotekanauki.pl/articles/31339301.pdf
    Data publikacji:
    2015-11-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    signed total (k
    k)-domatic number
    signed total k-dominating function
    signed total k-domination number
    regular graphs
    Opis:
    Let $G$ be a graph with vertex set $V (G)$, and let $ f : V (G) \rightarrow {−1, 1}$ be a two-valued function. If $ k \geq 1$ is an integer and \( \sum_{ x \in N(v)} f(x) \geq k \) for each $ v \in V (G) $, where $N(v)$ is the neighborhood of $v$, then $f$ is a signed total $k$-dominating function on $G$. A set ${f_1, f_2, . . ., f_d}$ of distinct signed total k-dominating functions on $G$ with the property that \( \sum_{i=1}^d f_i(x) \leq k \) for each $ x \in V (G)$, is called a signed total ($k$, $k$)-dominating family (of functions) on $G$. The maximum number of functions in a signed total ($k$, $k$)-dominating family on $G$ is the signed total ($k$, $k$)-domatic number of $G$. In this article we mainly present upper bounds on the signed total ($k$, $k$)- domatic number, in particular for regular graphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2015, 35, 4; 641-650
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On the Complexity of Reinforcement in Graphs
    Autorzy:
    Rad, Nader Jafari
    Powiązania:
    https://bibliotekanauki.pl/articles/31340751.pdf
    Data publikacji:
    2016-11-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    domination
    total domination
    total restrained domination
    p- domination
    k-rainbow domination
    reinforcement
    NP-hard
    Opis:
    We show that the decision problem for p-reinforcement, p-total rein- forcement, total restrained reinforcement, and k-rainbow reinforcement are NP-hard for bipartite graphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2016, 36, 4; 877-887
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    The Signed Total Roman k-Domatic Number Of A Graph
    Autorzy:
    Volkmann, Lutz
    Powiązania:
    https://bibliotekanauki.pl/articles/31341581.pdf
    Data publikacji:
    2017-11-27
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    signed total Roman k-dominating function
    signed total Roman k-domination number
    signed total Roman k-domatic number
    Opis:
    Let $ k \ge 1 $ be an integer. A signed total Roman $k$-dominating function on a graph $G$ is a function $ f : V (G) \rightarrow {−1, 1, 2} $ such that $ \Sigma_{ u \in N(v) } f(u) \ge k $ for every $ v \in V (G) $, where $ N(v) $ is the neighborhood of $ v $, and every vertex $ u \in V (G) $ for which $ f(u) = −1 $ is adjacent to at least one vertex w for which $ f(w) = 2 $. A set $ { f_1, f_2, . . ., f_d} $ of distinct signed total Roman $k$-dominating functions on $G$ with the property that $ \Sigma_{i=1}^d f_i(v) \le k $ for each $ v \in V (G) $, is called a signed total Roman $k$-dominating family (of functions) on $G$. The maximum number of functions in a signed total Roman $k$-dominating family on $G$ is the signed total Roman $k$-domatic number of $G$, denoted by $ d_{stR}^k (G) $. In this paper we initiate the study of signed total Roman $k$-domatic numbers in graphs, and we present sharp bounds for $ d_{stR}^k (G) $. In particular, we derive some Nordhaus-Gaddum type inequalities. In addition, we determine the signed total Roman $k$-domatic number of some graphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2017, 37, 4; 1027-1038
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    The k-rainbow domatic number of a graph
    Autorzy:
    Sheikholeslami, Seyyed
    Volkmann, Lutz
    Powiązania:
    https://bibliotekanauki.pl/articles/743715.pdf
    Data publikacji:
    2012
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    k-rainbow dominating function
    k-rainbow domination number
    k-rainbow domatic number
    Opis:
    For a positive integer k, a k-rainbow dominating function of a graph G is a function f from the vertex set V(G) to the set of all subsets of the set {1,2, ...,k} such that for any vertex v ∈ V(G) with f(v) = ∅ the condition ⋃_{u ∈ N(v)}f(u) = {1,2, ...,k} is fulfilled, where N(v) is the neighborhood of v. The 1-rainbow domination is the same as the ordinary domination. A set ${f₁,f₂, ...,f_d}$ of k-rainbow dominating functions on G with the property that $∑_{i = 1}^d |f_i(v)| ≤ k$ for each v ∈ V(G), is called a k-rainbow dominating family (of functions) on G. The maximum number of functions in a k-rainbow dominating family on G is the k-rainbow domatic number of G, denoted by $d_{rk}(G)$. Note that $d_{r1}(G)$ is the classical domatic number d(G). In this paper we initiate the study of the k-rainbow domatic number in graphs and we present some bounds for $d_{rk}(G)$. Many of the known bounds of d(G) are immediate consequences of our results.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2012, 32, 1; 129-140
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    The k-Rainbow Bondage Number of a Digraph
    Autorzy:
    Amjadi, Jafar
    Mohammadi, Negar
    Sheikholeslami, Seyed Mahmoud
    Volkmann, Lutz
    Powiązania:
    https://bibliotekanauki.pl/articles/31339490.pdf
    Data publikacji:
    2015-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    k-rainbow dominating function
    k-rainbow domination number
    k-rainbow bondage number
    digraph
    Opis:
    Let $ D = (V,A) $ be a finite and simple digraph. A $k$-rainbow dominating function ($ k \text{RDF} $) of a digraph $D$ is a function $f$ from the vertex set $V$ to the set of all subsets of the set ${1, 2, . . ., k}$ such that for any vertex $ v \in V $ with $ f(v) = \emptyset $ the condition \( \bigcup_{ u \in N^−(v) } f(u) = {1, 2, . . ., k} \) is fulfilled, where $ N^− (v) $ is the set of in-neighbors of $v$. The weight of a \( k \text{RDF} \) \( f \) is the value \( \omega (f) = \sum_{v \in V} |f(v)| \). The $k$-rainbow domination number of a digraph $D$, denoted by $ \gamma_{rk} (D) $, is the minimum weight of a $ k \text{RDF} $ of $D$. The $k$-rainbow bondage number $ b_{rk} (D) $ of a digraph $D$ with maximum in-degree at least two, is the minimum cardinality of all sets $ A^\prime \subseteq A $ for which $ \gamma_{rk} (D−A^\prime ) > \gamma_{rk} (D) $. In this paper, we establish some bounds for the $k$-rainbow bondage number and determine the $k$-rainbow bondage number of several classes of digraphs.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2015, 35, 2; 261-270
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Signed star (k, k)-domatic number of a graph
    Autorzy:
    Sheikholeslami, S. M.
    Volkmann, L.
    Powiązania:
    https://bibliotekanauki.pl/articles/254927.pdf
    Data publikacji:
    2014
    Wydawca:
    Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
    Tematy:
    signed star (k, k)-domatic number
    signed star domatic number
    signed star k-dominating function
    signed star dominating function
    signed star k-domination number
    signed star domination number
    regular graphs
    Opis:
    Let G be a simple graph without isolated vertices with vertex set V (G) and edge set E(G) and let k be a positive integer. A function ƒ: E(G) →{−1, 1} is said to be a signed star k-dominating function on [formula] for every vertex v of G, where E(v) = {uv ∈ E(G) | u ∈ N(v)}. A set {f1, f2, . . . , fd} of signed star k-dominating functions on G with the property that [formula] for each e ∈ E(G) is called a signed star (k, k)-dominating family (of functions) on G. The maximum number of functions in a signed star (k, k)-dominating family on G is the signed star (k, k)-domatic number of G, denoted by [formula]. In this paper we study properties of the signed star (k, k)-domatic number [formula]. In particular, we present bounds on [formula], and we determine the signed (k, k)-domatic number of some regular graphs. Some of our results extend these given by Atapour, Sheikholeslami, Ghameslou and Volkmann [Signed star domatic number of a graph, Discrete Appl. Math. 158 (2010), 213–218] for the signed star domatic number.
    Źródło:
    Opuscula Mathematica; 2014, 34, 3; 609-620
    1232-9274
    2300-6919
    Pojawia się w:
    Opuscula Mathematica
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    The Distance Roman Domination Numbers of Graphs
    Autorzy:
    Aram, Hamideh
    Norouzian, Sepideh
    Sheikholeslami, Seyed Mahmoud
    Powiązania:
    https://bibliotekanauki.pl/articles/30098151.pdf
    Data publikacji:
    2013-09-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    k-distance Roman dominating function
    k-distance Roman domination number
    Roman dominating function
    Roman domination number
    Opis:
    Let $ k $ be a positive integer, and let $ G $ be a simple graph with vertex set $ V (G) $. A k-distance Roman dominating function on $ G $ is a labeling $ f : V (G) → {0, 1, 2} $ such that for every vertex with label 0, there is a vertex with label 2 at distance at most $ k $ from each other. The weight of a $k$-distance Roman dominating function $ f $ is the value $ \omega (f) =∑_{v∈V} f(v) $. The k-distance Roman domination number of a graph $G$, denoted by $\gamma_R^k (D) $, equals the minimum weight of a $k$-distance Roman dominating function on G. Note that the 1-distance Roman domination number $ \gamma_R^1 (G) $ is the usual Roman domination number $ \gamma_R (G) $. In this paper, we investigate properties of the $k$-distance Roman domination number. In particular, we prove that for any connected graph $ G $ of order $ n \geq k +2$, $\gamma_R^k (G) \leq 4n//(2k +3) $ and we characterize all graphs that achieve this bound. Some of our results extend these ones given by Cockayne et al. in 2004 and Chambers et al. in 2009 for the Roman domination number.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2013, 33, 4; 717-730
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On the inverse signed total domination number in graphs
    Autorzy:
    Mojdeh, D. A.
    Samadi, B.
    Powiązania:
    https://bibliotekanauki.pl/articles/255392.pdf
    Data publikacji:
    2017
    Wydawca:
    Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
    Tematy:
    inverse signed total dominating function
    inverse signed total domination number
    k-tuple total domination number
    Opis:
    In this paper, we study the inverse signed total domination number in graphs and present new sharp lower and upper bounds on this parameter. For example by making use of the classic theorem of Turán (1941), we present a sharp upper bound on Kr+1-free graphs for r ≥ 2. Also, we bound this parameter for a tree from below in terms of its order and the number of leaves and characterize all trees attaining this bound.
    Źródło:
    Opuscula Mathematica; 2017, 37, 3; 447-456
    1232-9274
    2300-6919
    Pojawia się w:
    Opuscula Mathematica
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    3-Tuple Total Domination Number of Rook’s Graphs
    Autorzy:
    Pahlavsay, Behnaz
    Palezzato, Elisa
    Torielli, Michele
    Powiązania:
    https://bibliotekanauki.pl/articles/32361755.pdf
    Data publikacji:
    2022-02-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    k -tuple total domination
    Cartesian product of graphs
    rook’s graph
    Vizing’s conjecture
    Opis:
    A k-tuple total dominating set (kTDS) of a graph G is a set S of vertices in which every vertex in G is adjacent to at least k vertices in S. The minimum size of a kTDS is called the k-tuple total dominating number and it is denoted by γ×k,t(G). We give a constructive proof of a general formula for γ×3,t(Kn□Km).
    Źródło:
    Discussiones Mathematicae Graph Theory; 2022, 42, 1; 15-37
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Some properties of the zero divisor graph of a commutative ring
    Autorzy:
    Nazzal, Khalida
    Ghanem, Manal
    Powiązania:
    https://bibliotekanauki.pl/articles/729189.pdf
    Data publikacji:
    2014
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    automorphism group of a graph
    center of a graph
    core of a graph
    k-domination number
    Gaussian integers modulo n
    median of a graph
    2-packing
    perfect graph
    and zero divisor graph
    Opis:
    Let Γ(R) be the zero divisor graph for a commutative ring with identity. The k-domination number and the 2-packing number of Γ(R), where R is an Artinian ring, are computed. k-dominating sets and 2-packing sets for the zero divisor graph of the ring of Gaussian integers modulo n, Γ(ℤₙ[i]), are constructed. The center, the median, the core, as well as the automorphism group of Γ(ℤₙ[i]) are determined. Perfect zero divisor graphs Γ(R) are investigated.
    Źródło:
    Discussiones Mathematicae - General Algebra and Applications; 2014, 34, 2; 167-181
    1509-9415
    Pojawia się w:
    Discussiones Mathematicae - General Algebra and Applications
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    A Characterization of Trees for a New Lower Bound on the K-Independence Number
    Autorzy:
    Meddah, Nacéra
    Blidia, Mostafa
    Powiązania:
    https://bibliotekanauki.pl/articles/30146579.pdf
    Data publikacji:
    2013-05-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    domination
    independence
    k-independence
    Opis:
    Let $k$ be a positive integer and $G = (V,E)$ a graph of order $n$. A subset $S$ of $V$ is a $k$-independent set of $G$ if the maximum degree of the subgraph induced by the vertices of $S$ is less or equal to $k − 1$. The maximum cardinality of a $k$-independent set of $G$ is the $k$-independence number $\beta_k (G)$. In this paper, we show that for every graph $ G $, $\beta_k (G) \geq $ \( \lceil ( n + ( \chi(G)-1) \Sigma_{v \in S(G)} \min ( | L_v|, k-1) ) / \chi(G) \rceil \), where $\chi(G)$, $s(G)$ and $L_v$ are the chromatic number, the number of supports vertices and the number of leaves neighbors of $v$, in the graph $G$, respectively. Moreover, we characterize extremal trees attaining these bounds.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2013, 33, 2; 395-410
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On the Signed (Total) k-Independence Number in Graphs
    Autorzy:
    Khodkar, Abdollah
    Samadi, Babak
    Volkmann, Lutz
    Powiązania:
    https://bibliotekanauki.pl/articles/31234099.pdf
    Data publikacji:
    2015-11-01
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    domination in graphs
    signed k-independence
    limited packing
    tuple domination
    Opis:
    Let G be a graph. A function f : V (G) → {−1, 1} is a signed k- independence function if the sum of its function values over any closed neighborhood is at most k − 1, where k ≥ 2. The signed k-independence number of G is the maximum weight of a signed k-independence function of G. Similarly, the signed total k-independence number of G is the maximum weight of a signed total k-independence function of G. In this paper, we present new bounds on these two parameters which improve some existing bounds.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2015, 35, 4; 651-662
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    The complexity of open k-monopolies in graphs for negative k
    Autorzy:
    Peterin, Iztok
    Powiązania:
    https://bibliotekanauki.pl/articles/255938.pdf
    Data publikacji:
    2019
    Wydawca:
    Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
    Tematy:
    open k-monopolies
    complexity
    total domination
    Opis:
    Let G be a graph with vertex set V(G), δ (G) minimum degree of G and [formula]. Given a nonempty set M ⊆ V(G) a vertex v of G is said to be k-controlled by M if [formula] where δM(v) represents the number of neighbors of v in M. The set M is called an open k-monopoly for G if it fc-controls every vertex v of G. In this short note we prove that the problem of computing the minimum cardinality of an open k-monopoly in a graph for a negative integer k is NP-complete even restricted to chordal graphs.
    Źródło:
    Opuscula Mathematica; 2019, 39, 3; 425-431
    1232-9274
    2300-6919
    Pojawia się w:
    Opuscula Mathematica
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Connected global offensive k-alliances in graphs
    Autorzy:
    Volkmann, Lutz
    Powiązania:
    https://bibliotekanauki.pl/articles/743583.pdf
    Data publikacji:
    2011
    Wydawca:
    Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
    Tematy:
    alliances in graphs
    connected global offensive k-alliance
    global offensive k-alliance
    domination
    Opis:
    We consider finite graphs G with vertex set V(G). For a subset S ⊆ V(G), we define by G[S] the subgraph induced by S. By n(G) = |V(G) | and δ(G) we denote the order and the minimum degree of G, respectively. Let k be a positive integer. A subset S ⊆ V(G) is a connected global offensive k-alliance of the connected graph G, if G[S] is connected and |N(v) ∩ S | ≥ |N(v) -S | + k for every vertex v ∈ V(G) -S, where N(v) is the neighborhood of v. The connected global offensive k-alliance number $γₒ^{k,c}(G)$ is the minimum cardinality of a connected global offensive k-alliance in G.
    In this paper we characterize connected graphs G with $γₒ^{k,c}(G) = n(G)$. In the case that δ(G) ≥ k ≥ 2, we also characterize the family of connected graphs G with $γₒ^{k,c}(G) = n(G) - 1$. Furthermore, we present different tight bounds of $γₒ^{k,c}(G)$.
    Źródło:
    Discussiones Mathematicae Graph Theory; 2011, 31, 4; 699-707
    2083-5892
    Pojawia się w:
    Discussiones Mathematicae Graph Theory
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    On uniform strict minima for vector-valued functions
    Autorzy:
    Bednarczuk, E. M.
    Leśniewski, K.
    Powiązania:
    https://bibliotekanauki.pl/articles/206852.pdf
    Data publikacji:
    2015
    Wydawca:
    Polska Akademia Nauk. Instytut Badań Systemowych PAN
    Tematy:
    uniform strict minima
    K-convex mappings
    metric subregularity
    domination property
    Opis:
    We introduce uniform strict minima for vector-valued functions and provide conditions for their Lipschitz continuity as functions of linear perturbations. We also investigate regularity propertiesof subdifferentialsfor cone convexvector-valuedfunctions.
    Źródło:
    Control and Cybernetics; 2015, 44, 2; 257-273
    0324-8569
    Pojawia się w:
    Control and Cybernetics
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
    Tytuł:
    Outer independent rainbow dominating functions in graphs
    Autorzy:
    Mansouri, Zhila
    Mojdeh, Doost Ali
    Powiązania:
    https://bibliotekanauki.pl/articles/1397885.pdf
    Data publikacji:
    2020
    Wydawca:
    Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
    Tematy:
    outer-independent rainbow domination
    K1
    r -free graphs
    trees
    Opis:
    A 2-rainbow dominating function (2-rD function) of a graph G = (V, E) is a function $ f : V(G) \rightarrow \{ \emptyset, \{1\}, \{2\}, \{1, 2\}\}$ having the property that if $f(x) = \emptyset$, then $f(N(x))= \{1,2\}$. The 2-rainbow domination number $\gamma_{r2}(G)$ is the minimum weight of $ \sum_{v \in V(G)} |f(v)| $ taken over all 2-rainbow dominating functions $f$. An outer-independent 2-rainbow dominating function (OI2-rD function) of a graph G is a 2-rD function $f$ for which the set of all $ v \in V(G)$ with $ f(v)=\emptyset $ is independent. The outer independent 2-rainbow domination number [formula] is the minimum weight of an OI2-rD function of G. In this paper, we study the OI2-rD number of graphs. We give the complexity of the problem OI2-rD of graphs and present lower and upper bounds on $\gamma_{oir2} (G) $. Moreover, we characterize graphs with some small or large OI2-rD numbers and we also bound this parameter from above for trees in terms of the order, leaves and the number of support vertices and characterize all trees attaining the bound. Finally, we show that any ordered pair (a, b) is realizable as the vertex cover number and OI2-rD numbers of some non-trivial tree if and only if $a+1 \leq b \leq 2a $.
    Źródło:
    Opuscula Mathematica; 2020, 40, 5; 599-615
    1232-9274
    2300-6919
    Pojawia się w:
    Opuscula Mathematica
    Dostawca treści:
    Biblioteka Nauki
    Artykuł
      Wyświetlanie 1-31 z 31

      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