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

  Lista filtrów
Wyrównaj
Wyświetlanie 1-15 z 19
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ł:
Weak roman domination in graphs
Autorzy:
Roushini Leely Pushpam, P.
Malini Mai, T.
Powiązania:
https://bibliotekanauki.pl/articles/743835.pdf
Data publikacji:
2011
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination number
weak Roman domination number
Opis:
Let G = (V,E) be a graph and f be a function f:V → {0,1,2}. A vertex u with f(u) = 0 is said to be undefended with respect to f, if it is not adjacent to a vertex with positive weight. The function f is a weak Roman dominating function (WRDF) if each vertex u with f(u) = 0 is adjacent to a vertex v with f(v) > 0 such that the function f': V → {0,1,2} defined by f'(u) = 1, f'(v) = f(v)-1 and f'(w) = f(w) if w ∈ V-{u,v}, has no undefended vertex. The weight of f is $w(f) = ∑_{v ∈ V}f(v)$. The weak Roman domination number, denoted by $γ_r(G)$, is the minimum weight of a WRDF in G. In this paper, we characterize the class of trees and split graphs for which $γ_r(G) = γ(G)$ and find $γ_r$-value for a caterpillar, a 2×n grid graph and a complete binary tree.
Źródło:
Discussiones Mathematicae Graph Theory; 2011, 31, 1; 161-170
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Total Roman Reinforcement in Graphs
Autorzy:
Ahangar, H. Abdollahzadeh
Amjadi, J.
Chellali, M.
Nazari-Moghaddam, S.
Sheikholeslami, S.M.
Powiązania:
https://bibliotekanauki.pl/articles/31343238.pdf
Data publikacji:
2019-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
total Roman domination number
total Roman reinforcement number
Opis:
A total Roman dominating function on a graph G is a labeling f : V (G) → {0, 1, 2} such that every vertex with label 0 has a neighbor with label 2 and the subgraph of G induced by the set of all vertices of positive weight has no isolated vertex. The minimum weight of a total Roman dominating function on a graph G is called the total Roman domination number of G. The total Roman reinforcement number rtR(G) of a graph G is the minimum number of edges that must be added to G in order to decrease the total Roman domination number. In this paper, we investigate the proper- ties of total Roman reinforcement number in graphs, and we present some sharp bounds for rtR(G). Moreover, we show that the decision problem for total Roman reinforcement is NP-hard for bipartite graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2019, 39, 4; 787-803
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 Double Roman Domatic Number of a Digraph
Autorzy:
Volkmann, Lutz
Powiązania:
https://bibliotekanauki.pl/articles/31348166.pdf
Data publikacji:
2020-11-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
digraph
double Roman domination
double Roman domatic number
Opis:
A double Roman dominating function on a digraph $D$ with vertex set $V(D)$ is defined in [G. Hao, X. Chen and L. Volkmann, Double Roman domination in digraphs, Bull. Malays. Math. Sci. Soc. (2017).] as a function $f : V (D) → {0, 1, 2, 3}$ having the property that if $f(v) = 0$, then the vertex $v$ must have at least two in-neighbors assigned 2 under $f$ or one in-neighbor w with $f(w) = 3$, and $if f(v) = 1$, then the vertex v must have at least one in-neighbor $u$ with $f(u) ≥ 2$. A set ${f_1, f_2, . . ., f_d}$ of distinct double Roman dominating functions on $D$ with the property that $∑_{i=1}^df_i(v)≤3$ for each $v ∈ V (D)$ is called a double Roman dominating family (of functions) on $D$. The maximum number of functions in a double Roman dominating family on $D$ is the double Roman domatic number of $D$, denoted by $d_{dR}(D)$. We initiate the study of the double Roman domatic number, and we present different sharp bounds on $d_{dR}(D)$. In addition, we determine the double Roman domatic number of some classes of digraphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2020, 40, 4; 995-1004
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
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ł:
Signed Total Roman Edge Domination In Graphs
Autorzy:
Asgharsharghi, Leila
Sheikholeslami, Seyed Mahmoud
Powiązania:
https://bibliotekanauki.pl/articles/31341578.pdf
Data publikacji:
2017-11-27
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
signed total Roman dominating function
signed total Roman domination number
signed total Roman edge dominating function
signed total Roman edge domination number
Opis:
Let $ G = (V,E) $ be a simple graph with vertex set $V$ and edge set $E$. A signed total Roman edge dominating function of $G$ is a function $ f : E \rightarrow {−1, 1, 2} $ satisfying the conditions that (i) $ \Sigma_{e^′ \in N(e)} f(e^′) \ge 1 $ for each $ e \in E $, where $N(e)$ is the open neighborhood of $e$, and (ii) every edge $e$ for which $f(e) = −1$ is adjacent to at least one edge $ e^′$ for which $f(e^′) = 2$. The weight of a signed total Roman edge dominating function $f$ is $ \omega(f) = \Sigma_{e \in E } f(e) $. The signed total Roman edge domination number $ \gamma_{stR}^' (G) $ of $G$ is the minimum weight of a signed total Roman edge dominating function of $G$. In this paper, we first prove that for every tree $T$ of order $ n \ge 4 $, $ \gamma_{stR}^' (T) \ge \frac{17−2n}{5} $ and we characterize all extreme trees, and then we present some sharp bounds for the signed total Roman edge domination number. We also determine this parameter for some classes of graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2017, 37, 4; 1039-1053
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Signed Total Roman Domination in Digraphs
Autorzy:
Volkmann, Lutz
Powiązania:
https://bibliotekanauki.pl/articles/31342127.pdf
Data publikacji:
2017-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
digraph
signed total Roman dominating function
signed total Roman domination number
Opis:
Let $D$ be a finite and simple digraph with vertex set $V (D)$. A signed total Roman dominating function (STRDF) 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 1 $ for each $ v \in V (D) $, where $ N^− (v) $ consists of all vertices of $D$ from which arcs go into $v$, and (ii) every vertex u for which $f(u) = −1$ has an inner neighbor $v$ for which $f(v) = 2$. The weight of an STRDF $f$ is $ w(f) = \Sigma_{ v \in V } (D) f(v) $. The signed total Roman domination number $ \gamma_{stR} (D) $ of $D$ is the minimum weight of an STRDF on $D$. In this paper we initiate the study of the signed total Roman domination number of digraphs, and we present different bounds on $ \gamma_{stR} (D) $. In addition, we determine the signed total Roman domination number of some classes of digraphs. Some of our results are extensions of known properties of the signed total Roman domination number $ \gamma_{stR} (G)$ of graphs $G$.
Źródło:
Discussiones Mathematicae Graph Theory; 2017, 37, 1; 261-272
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ł:
Roman {2}-Bondage Number of a Graph
Autorzy:
Moradi, Ahmad
Mojdeh, Doost Ali
Sharifi, Omid
Powiązania:
https://bibliotekanauki.pl/articles/32083773.pdf
Data publikacji:
2020-02-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
Roman {2}-domination
Roman {2}-bondage number
Opis:
For a given graph G=(V, E), a Roman {2}-dominating function f : V (G) → {0, 1, 2} has the property that for every vertex u with f(u) = 0, either u is adjacent to a vertex assigned 2 under f, or is adjacent to at least two vertices assigned 1 under f. The Roman {2}-domination number of G, γ{R2}(G), is the minimum of Σu∈V (G) f(u) over all such functions. In this paper, we initiate the study of the problem of finding Roman {2}-bondage number of G. The Roman {2}-bondage number of G, b{R2}, is defined as the cardinality of a smallest edge set E′ ⊆ E for which γ{R2}(G − E′) > γ{R2}(G). We first demonstrate complexity status of the problem by proving that the problem is NP-Hard. Then, we derive useful parametric as well as fixed upper bounds on the Roman {2}-bondage number of G. Specifically, it is known that the Roman bondage number of every planar graph does not exceed 15 (see [S. Akbari, M. Khatirinejad and S. Qajar, A note on the Roman bondage number of planar graphs, Graphs Combin. 29 (2013) 327–331]). We show that same bound will be preserved while computing the Roman {2}-bondage number of such graphs. The paper is then concluded by computing exact value of the parameter for some classes of graphs.
Źródło:
Discussiones Mathematicae Graph Theory; 2020, 40, 1; 255-268
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Roman bondage in graphs
Autorzy:
Rad, Nader
Volkmann, Lutz
Powiązania:
https://bibliotekanauki.pl/articles/743601.pdf
Data publikacji:
2011
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
domination
Roman domination
Roman bondage number
Opis:
A Roman dominating function on a graph G is a function f:V(G) → {0,1,2} satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. The weight of a Roman dominating function is the value $f(V(G)) = ∑_{u ∈ V(G)}f(u)$. The Roman domination number, $γ_R(G)$, of G is the minimum weight of a Roman dominating function on G. In this paper, we define the Roman bondage $b_R(G)$ of a graph G with maximum degree at least two to be the minimum cardinality of all sets E' ⊆ E(G) for which $γ_R(G -E') > γ_R(G)$. We determine the Roman bondage number in several classes of graphs and give some sharp bounds.
Źródło:
Discussiones Mathematicae Graph Theory; 2011, 31, 4; 763-773
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On The Total Roman Domination in Trees
Autorzy:
Amjadi, Jafar
Sheikholeslami, Seyed Mahmoud
Soroudi, Marzieh
Powiązania:
https://bibliotekanauki.pl/articles/31343413.pdf
Data publikacji:
2019-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
total Roman dominating function
total Roman domination number
trees
Opis:
A total Roman dominating function on a graph G is a function f : V (G) → {0, 1, 2} satisfying the following conditions: (i) every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2 and (ii) the subgraph of G induced by the set of all vertices of positive weight has no isolated vertex. The weight of a total Roman dominating function f is the value f(V (G)) = Σu∈V(G) f(u). The total Roman domination number γtR(G) is the minimum weight of a total Roman dominating function of G. Ahangar et al. in [H.A. Ahangar, M.A. Henning, V. Samodivkin and I.G. Yero, Total Roman domination in graphs, Appl. Anal. Discrete Math. 10 (2016) 501–517] recently showed that for any graph G without isolated vertices, 2γ(G) ≤ γtR(G) ≤ 3γ(G), where γ(G) is the domination number of G, and they raised the problem of characterizing the graphs G achieving these upper and lower bounds. In this paper, we provide a constructive characterization of these trees.
Źródło:
Discussiones Mathematicae Graph Theory; 2019, 39, 2; 519-532
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On The Roman Domination Stable Graphs
Autorzy:
Hajian, Majid
Rad, Nader Jafari
Powiązania:
https://bibliotekanauki.pl/articles/31341613.pdf
Data publikacji:
2017-11-27
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Roman domination number
bound
Opis:
A Roman dominating function (or just RDF) on a graph $ G = (V,E) $ is a function $ f : V \rightarrow \{ 0, 1, 2 \} $ satisfying the condition that every vertex $u$ for which $f(u) = 0$ is adjacent to at least one vertex $v$ for which $f(v) = 2$. The weight of an RDF $f$ is the value $f(V (G)) = \Sigma_{ u \in V(G) } f(u) $. The Roman domination number of a graph $G$, denoted by $ \gamma_R (G)$, is the minimum weight of a Roman dominating function on $G$. A graph $G$ is Roman domination stable if the Roman domination number of $G$ remains unchanged under removal of any vertex. In this paper we present upper bounds for the Roman domination number in the class of Roman domination stable graphs, improving bounds posed in [V. Samodivkin, Roman domination in graphs: the class $ R_{UV R} $, Discrete Math. Algorithms Appl. 8 (2016) 1650049].
Źródło:
Discussiones Mathematicae Graph Theory; 2017, 37, 4; 859-871
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
On The Co-Roman Domination in Graphs
Autorzy:
Shao, Zehui
Sheikholeslami, Seyed Mahmoud
Soroudi, Marzieh
Volkmann, Lutz
Liu, Xinmiao
Powiązania:
https://bibliotekanauki.pl/articles/31343438.pdf
Data publikacji:
2019-05-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
co-Roman dominating function
co-Roman domination number
Roman domination
Opis:
Let $G = (V, E)$ be a graph and let $f : V (G) \rightarrow {0, 1, 2}$ be a function. A vertex $v$ is said to be protected with respect to $f$, if $f(v) > 0$ or $f(v) = 0$ and $v$ is adjacent to a vertex of positive weight. The function $f$ is a co-Roman dominating function if (i) every vertex in $V$ is protected, and (ii) each $ v \in V $ with positive weight has a neighbor $ u \in V $ with $ f(u) = 0 $ such that the function $ f_{uv} : V \rightarrow {0, 1, 2} $, defined by $ f_{uv} (u) = 1$, $ f_{uv}(v) = f(v) − 1$ and $ f_{uv}(x) = f(x)$ for $ x \in V \backslash \{ v, u \} $, has no unprotected vertex. The weight of $f$ is $ \omega(f) = \Sigma_{ v \in V } f(v) $. The co-Roman domination number of a graph $G$, denoted by $ \gamma_{cr}(G) $, is the minimum weight of a co-Roman dominating function on $G$. In this paper, we give a characterization of graphs of order $n$ for which co-Roman domination number is \( \tfrac{2n}{3} \) or $n − 2$, which settles two open problem in [S. Arumugam, K. Ebadi and M. Manrique, Co-Roman domination in graphs, Proc. Indian Acad. Sci. Math. Sci. 125 (2015) 1–10]. Furthermore, we present some sharp bounds on the co-Roman domination number.
Źródło:
Discussiones Mathematicae Graph Theory; 2019, 39, 2; 455-472
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Tytuł:
Extremal Graphs for a Bound on the Roman Domination Number
Autorzy:
Bouchou, Ahmed
Blidia, Mostafa
Chellali, Mustapha
Powiązania:
https://bibliotekanauki.pl/articles/31513493.pdf
Data publikacji:
2020-08-01
Wydawca:
Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:
Roman domination
Roman domination number
Nordhaus-Gaddum inequalities
Opis:
A Roman dominating function on a graph G = (V, E) is a function f:V (G) → {0, 1, 2} such that every vertex u for which f(u) = 0 is adjacent to at least one vertex v with f(v) = 2. The weight of a Roman dominating function is the value w(f) = Σu∈V(G) f(u). The minimum weight of a Roman dominating function on a graph G is called the Roman domination number of G, denoted by γR(G). In 2009, Chambers, Kinnersley, Prince and West proved that for any graph G with n vertices and maximum degree Δ, γR(G) ≤ n + 1 − Δ. In this paper, we give a characterization of graphs attaining the previous bound including trees, regular and semiregular graphs. Moreover, we prove that the problem of deciding whether γR(G) = n + 1 − Δ is co-complete. Finally, we provide a characterization of extremal graphs of a Nordhaus–Gaddum bound for γR(G) + γR (Ḡ), where Ḡ is the complement graph of G.
Źródło:
Discussiones Mathematicae Graph Theory; 2020, 40, 3; 771-785
2083-5892
Pojawia się w:
Discussiones Mathematicae Graph Theory
Dostawca treści:
Biblioteka Nauki
Artykuł
Wyświetlanie 1-15 z 19

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