The present reprint contains twelve papers published in the Special Issue “Advances in Discrete Applied Mathematics and Graph Theory, 2021” of the MDPI Mathematics journal, which cover a wide range ...of topics connected to the theory and applications of Graph Theory and Discrete Applied Mathematics. The focus of the majority of papers is on recent advances in graph theory and applications in chemical graph theory. In particular, the topics studied include bipartite and multipartite Ramsey numbers, graph coloring and chromatic numbers, several varieties of domination (Double Roman, Quasi-Total Roman, Total 3-Roman) and two graph indices of interest in chemical graph theory (Sombor index, generalized ABC index), as well as hyperspaces of graphs and local inclusive distance vertex irregular graphs.
For a graph G=(V,E), a Roman {2}-dominating function (R2DF) f:V→{0,1,2} has the property that for every vertex v∈V with f(v)=0, either there exists an adjacent vertex, a neighbor u∈N(v), with f(u)=2, ...or at least two neighbors x,y∈N(v) having f(x)=f(y)=1. The weight of a R2DF is the sum f(V)=∑v∈Vf(v). A R2DF f=(V0,V1,V2) is called independent if V1∪V2 is an independent set. The independent Roman {2}-domination number i{R2}(G) is the minimum weight of an IR2DF on G. In this paper, we show that the decision problem associated with i{R2}(G) is NP-complete even when restricted to bipartite graphs. Then we show that for every graph G of order n, 0≤ir2(G)−i{R2}(G)≤n∕5 and 0≤iR(G)−i{R2}(G)≤n∕4, where ir2(G) and iR(G) are the independent 2-rainbow domination and independent Roman domination numbers, respectively. Moreover, we prove that the equality i{R2}(G)=ir2(G) holds for trees.
Outer independent double Roman domination Abdollahzadeh Ahangar, H.; Chellali, M.; Sheikholeslami, S.M.
Applied mathematics and computation,
01/2020, Letnik:
364
Journal Article
Recenzirano
An outer independent double Roman dominating function (OIDRDF) of a graph G is a function h from V(G) to {0, 1, 2, 3} for which each vertex with label 0 is adjacent to a vertex with label 3 or at ...least two vertices with label 2, and each vertex with label 1, is adjacent to a vertex with label greater than 1; and all vertices labeled by 0 is independent. The weight of an OIDRDF h is ∑w ∈ V(G)h(w), and the outer independent double Roman domination number γoidR(G) is the minimum weight of an OIDRDF on G. In this article, we provide various bounds on γoidR(G) and we show that its determining is NP-complete on chordal and bipartite graphs. Moreover, we establish Nordhaus–Gaddum bounds for γoidR(G)+γoidR(G¯).
The stability of dominating sets in Graphs is introduced and studied, in this paper. Here D is a dominating set of Graph G. In this paper the vertices of D and vertices of V - D are called donors and ...acceptors respectively. For a vertex u in D, let \psi_{D}(u) denote the number \|N(u) \cap (V - D)\|. The donor instability or simply d- instabilityd^{D}_{inst}(e)of an edge e connecting two donor vertices v and u is\|\psi_{D}(u)-\psi_{D}(v)\|. The d-instability of D,\psi_{d}(D) is the sum of d-instabilities of all edges connecting vertices in D. For a vertex u not in D, let \phi_{D}(u) denote the number\|N(u)\cap D\|. The Acceptor Instability or simply a-instability a^{D}_{inst}(e) of an edge e connecting two acceptor vertices u and v is \|\phi_{D}(u)-\phi_{D}(v)\|. The a-instability of D, \phi_{a}(D) is the sum of a-instabilities of all edges connecting vertices in V - D. The dominating set D is d-stable if \psi_{d}(D) = 0 and a-stable if \phi_{a}(D) = 0. D is stable, if \psi_{d}(D) = 0 and \psi_{a}(D) = 0. Given a non negative integer #α, D isα-d-stable, ifd^{D}_{inst}(e)\leqαfor any edge e connecting two donor vertices and D isα-a-stable, ifa^{D}_{inst}(e)\leqαfor any edge e connecting two acceptor vertices. Here we studyα- stability number of graphs for non negative integerα$.
In a graph G, a vertex dominates itself and its neighbours. A subset S⊆V(G) is said to be a double dominating set of G if S dominates every vertex of G at least twice. The minimum cardinality among ...all double dominating sets of G is the double domination number. In this article, we obtain tight bounds and closed formulas for the double domination number of lexicographic product graphs G∘H in terms of invariants of the factor graphs G and H.
Paired-domination game played in graphs T.W. Haynes; Michael A. Henning
Communications in combinatorics and optimization,
12/2019, Letnik:
4, Številka:
2
Journal Article
Recenzirano
Odprti dostop
In this paper, we continue the study of the domination game in graphs introduced by Bre{\v{s}}ar, Klav{\v{z}}ar, and Rall SIAM J. Discrete Math. 24 (2010) 979--991. We study the paired-domination ...version of the domination game which adds a matching dimension to the game. This game is played on a graph $G$ by two players, named Dominator and Pairer. They alternately take turns choosing vertices of $G$ such that each vertex chosen by Dominator dominates at least one vertex not dominated by the vertices previously chosen, while each vertex chosen by Pairer is a vertex not previously chosen that is a neighbor of the vertex played by Dominator on his previous move. This process eventually produces a paired-dominating set of vertices of $G$; that is, a dominating set in $G$ that induces a subgraph that contains a perfect matching. Dominator wishes to minimize the number of vertices chosen, while Pairer wishes to maximize it. The game paired-domination number $\gpr(G)$ of $G$ is the number of vertices chosen when Dominator starts the game and both players play optimally. Let $G$ be a graph on $n$ vertices with minimum degree at least~$2$. We show that $\gpr(G) \le \frac{4}{5}n$, and this bound is tight. Further we show that if $G$ is $(C_4,C_5)$-free, then $\gpr(G) \le \frac{3}{4}n$, where a graph is $(C_4,C_5)$-free if it has no induced $4$-cycle or $5$-cycle. If $G$ is $2$-connected and bipartite or if $G$ is $2$-connected and the sum of every two adjacent vertices in $G$ is at least~$5$, then we show that $\gpr(G) \le \frac{3}{4}n$.
Let G be non-trivial graph. A subset D of the vertex set V (G) of a graph G is called a dominating set of G if every vertex in V − D is adjacent to a vertex in D. The minimum cardinality of a ...dominating set is called the domination number and is denoted by γ(G). If V −D contains a dominating set S of G, then S is called an inverse dominating set with respect to D. In an inverse dominating set S, every pair of vertices u and v in S such that (degu, degv) = 1, then S is called relatively prime inverse dominating set. The minimum cardinality of a relatively prime inverse dominating set is called relatively prime inverse dominating number and is denoted by γ −1 rp (G). In this paper we find relatively prime inverse dominating number of some line graphs.
Total double Roman domination in graphs Guoliang Hao; Lutz Volkmann; Doost Ali Mojdeh
Communications in combinatorics and optimization,
06/2020, Letnik:
5, Številka:
1
Journal Article
Recenzirano
Odprti dostop
Let $G$ be a simple graph with vertex set $V$. A double Roman dominating function (DRDF) on $G$ is a function $f:V\rightarrow\{0,1,2,3\}$ satisfying that if $f(v)=0$, then the vertex $v$ must be ...adjacent to at least two vertices assigned $2$ or one vertex assigned $3$ under $f$, whereas if $f(v)=1$, then the vertex $v$ must be adjacent to at least one vertex assigned $2$ or $3$. The weight of a DRDF $f$ is the sum $\sum_{v\in V}f(v)$. A total double Roman dominating function (TDRDF) on a graph $G$ with no isolated vertex is a DRDF $f$ on $G$ with the additional property that the subgraph of $G$ induced by the set $\{v\in V:f(v)\ne0\}$ has no isolated vertices. The total double Roman domination number $\gamma_{tdR}(G)$ is the minimum weight of a TDRDF on $G$. In this paper, we give several relations between the total double Roman domination number of a graph and other domination parameters and we determine the total double Roman domination number of some classes of graphs.
Let G be a graph with no isolated vertex. A function f:V(G)→{0,1,2} is a total {2}-dominating function on G if ∑u∈N(v)f(u)≥2 for every vertex v∈V(G). The total {2}-domination number of G, denoted by ...γ{2},t(G), is the minimum weight ω(f)=∑v∈V(G)f(v) among all total {2}-dominating functions on G. It is known that for any graph G with no isolated vertex, γt(G)+1≤γ{2},t(G)≤2γt(G), where γt(G) represents the classical total domination number of G. In this paper, we first improve the previous lower bound, and as a consequence, we give necessary conditions for the graphs which satisfy this equality. Finally, we prove that any nontrivial tree T satisfies the equality in the upper bound, i.e., γ{2},t(T)=2γt(T).
Maximal double Roman domination in graphs Abdollahzadeh Ahangar, H.; Chellali, M.; Sheikholeslami, S.M. ...
Applied mathematics and computation,
02/2022, Letnik:
414
Journal Article
Recenzirano
•We introduce maximal double Roman dominating functions in graphs and study the corresponding parameter γdRm(G).•We show that the problem of determining γdRm(G) is NP-complete for bipartite, chordal ...and planar graphs. But it is solvable in linear time for bounded clique-width graphs including trees, cographs and distance-hereditary graphs.•We establish various relationships relating γdRm(G) to some domination parameters.•For the class of trees, we show that for every tree T of order n≥4,γdRm(T)≤54n and we characterize all trees attaining the bound.•Finally, the exact values of γdRm(G) are given for paths and cycles.
A maximal double Roman dominating function (MDRDF) on a graph G=(V,E) is a function f:V(G)→{0,1,2,3} such that (i) every vertex v with f(v)=0 is adjacent to least two vertices assigned 2 or to at least one vertex assigned 3, (ii) every vertex v with f(v)=1 is adjacent to at least one vertex assigned 2 or 3 and (iii) the set {w∈V|f(w)=0} is not a dominating set of G. The weight of a MDRDF is the sum of its function values over all vertices, and the maximal double Roman domination number γdRm(G) is the minimum weight of an MDRDF on G. In this paper, we initiate the study of maximal double Roman domination. We first show that the problem of determining γdRm(G) is NP-complete for bipartite, chordal and planar graphs. But it is solvable in linear time for bounded clique-width graphs including trees, cographs and distance-hereditary graphs. Moreover, we establish various relationships relating γdRm(G) to some domination parameters. For the class of trees, we show that for every tree T of order n≥4,γdRm(T)≤54n and we characterize all trees attaining the bound. Finally, the exact values of γdRm(G) are given for paths and cycles.
PDF
