Search

In response to a community prediction challenge, we simulate the nonadiabatic dynamics of cyclobutanone using the mapping approach to surface hopping (MASH). We consider the first 500 fs of relaxation following photoexcitation to the S2 state and predict the corresponding time-resolved electron-diffraction signal that will be measured by the planned experiment. 397 ab initio trajectories were obtained on the fly with state-averaged complete active space self-consistent field using a (12,11) active space. To obtain an estimate of the potential systematic error, 198 of the trajectories were calculated using an aug-cc-pVDZ basis set and 199 with a 6-31+G* basis set. MASH is a recently proposed independent trajectory method for simulating nonadiabatic dynamics, originally derived for two-state problems. As there are three relevant electronic states in this system, we used a newly developed multi-state generalization of MASH for the simulation: the uncoupled spheres multi-state MASH method (unSMASH). This study, therefore, serves both as an investigation of the photodissociation dynamics of cyclobutanone, and also as a demonstration of the applicability of unSMASH to ab initio simulations. In line with previous experimental studies, we observe that the simulated dynamics is dominated by three sets of dissociation products, C3H6 + CO, C2H4 + C2H2O, and C2H4 + CH2 + CO, and we interpret our predicted electron-diffraction signal in terms of the key features of the associated dissociation pathways. [ABSTRACT FROM AUTHOR]

In a graph G = (V , E) , a non-empty set A of k distinct vertices, is called a k - attack on G. The vertices in the set A are considered to be under attack. A set D ⊆ V can defend or counter the attack A on G if there exists a one-to-one function f : A ⟼ D , such that either f (u) = u or there is an edge between u , and its image f (u) , in G. A set D is called a k - defensive dominating set if it defends against any k -attack on G. Given a graph G = (V , E) , the minimum k -defensive domination problem requires us to compute a minimum cardinality k -defensive dominating set of G. When k is not fixed, it is co-NP-hard to decide if D ⊆ V is a k -defensive dominating set. However, when k is fixed, the decision version of the problem is NP-complete for general graphs. On the positive side, the problem can be solved in linear time when restricted to paths, cycles, co-chain, and threshold graphs for any k. This paper mainly focuses on the problem when k > 0 is fixed. We prove that the decision version of the problem remains NP-complete for bipartite graphs; this answers a question asked by Ekim et al. (Discrete Math. 343 (2) (2020)). We establish a lower and upper bound on the approximation ratio for the problem. Further, we show that the minimum k -defensive domination problem is APX-complete for bounded degree graphs. On the positive side, we show that the problem is efficiently solvable for complete bipartite graphs for any k > 0. Towards the end, we study a relationship between the defensive domination number and another well-studied domination parameter. [ABSTRACT FROM AUTHOR]

A double Roman dominating function on a graph G = (V,E) is a function g : V →{0, 1, 2, 3} satisfying the conditions that if g(v) = 0, then every vertex v is adjacent to minimum one vertex u for which g(u) = 3 or two vertices v and w for which g(v) = g(w) = 2 and if g(v) = 1, then v is adjacent to minimum one vertex w for which g(w) = 3 or 2. The weight of a double Roman dominating function denoted as w(g) is defined as w(g) =∑v∈V (G)g(v). The double Roman domination number denoted as γdR(G) is the minimum weight of double Roman dominating function on G. In this paper, we determine the γdR-value of some graphs such as Comb, Closed Helm, Comet, Double Comet, Lollipop, Helm, Double Comb and Jelly fish graphs. [ABSTRACT FROM AUTHOR]

Given two graphs G and H, their modular product G ⋄ H is defined to be the graph with V (G ⋄ H) = V (G) × V (H) and E (G ⋄ H) = E (G □ H) ∪ E (G × H) ∪ E (G ¯ × H ¯) . A dominating set of G is any set D ⊆ V (G) such that every vertex of G not contained in D has a neighbor in D. A total dominating set of G is a dominating set D of G with the additional property that all vertices of D also have a neighbor in D. The domination number γ (G) (resp. total domination number γ t (G) ) of G is the cardinality of a smallest dominating set (resp. total dominating set) of G. In this work we give several upper and lower bounds for γ (G ⋄ H) in terms of γ (G) , γ (H) , γ t (G ¯) and γ t (H ¯) , where G ¯ is the complement graph of G. Further, we fully describe graphs where γ (G ⋄ H) = k for k ∈ { 1 , 2 , 3 } . Several conditions on G and H under which γ (G ⋄ H) is at most 4 and 5 are also given. A new type of simultaneous domination γ ¯ (G) , defined as the smallest number of vertices that dominates G and totally dominates the complement of G, emerged as useful and we believe it could be of independent interest. We conclude the paper by proposing few directions for possible further research. [ABSTRACT FROM AUTHOR]

A set D of vertices in a graph G is a dominating set of G if every vertex not in D has a neighbor in D, where two vertices are neighbors if they are adjacent. If the dominating set D of G has the additional property that the subgraph induced by D contains a perfect matching (not necessarily as an induced subgraph), then D is a paired dominating set of G. The paired domination number of G, denoted by γ pr (G) , is the minimum cardinality of a paired dominating set of G. A set D ⊆ V (G) is a double dominating set of G if every vertex in V (G) \ D has at least two neighbors in D, and every vertex in D has a neighbor in D. The double domination number of G, denoted by γ × 2 (G) , is the minimum cardinality of a double dominating set of G. Chellali and Haynes (Util Math 67:161–171, (2005)) showed that if G is a claw-free graph without isolated vertices, then the paired domination number of G is at most the double domination number of G. In this paper, we show that if G is a H-free graph for some H ∈ { P 5 , 2 K 2 ∪ K 1 , fork } without isolated vertices, then γ pr (G) ≤ γ × 2 (G) . [ABSTRACT FROM AUTHOR]

Given a graph G with vertex set V, a dominating set S ⊆ V is a co-secure dominating set of G if for every vertex u ∈ S , there is a vertex v ∈ V \ S adjacent to u such that (S \ { u }) ∪ { v } is a dominating set of G. The minimum co-secure dominating set (or, for short, MCSDS) problem asks to find an MCSDS in a given graph. In this paper, first we show that the decision version of the problem is NP-complete in grid graphs and supergrid graphs. Consequently, we show that the problem remains NP-complete for unit disk and unit square graphs. Secondly, we show that the MCSDS problem is APX-hard in d-box graphs for any fixed integer d ≥ 2 . Finally, we give an O (n + m) time 2 (t - 1) -approximation algorithm for the MCSDS problem in several geometric intersection graphs which are K 1 , t -free for some integer t ≥ 3 . [ABSTRACT FROM AUTHOR]

In many fields, including science, technology, engineering, and communication networks, the idea of domination is used. Double domination is a widely recognized idea of domination concept in graph theory. A prominent crucial factor in network architecture is integrity. A subset S of V (G) is called a double dominating set of G if each vertex of G is dominated at least twice by S. In this paper, an algorithm to compute the double domination integrity of graphs is given. Also, an application of double domination integrity in the optimal phasor measurement unit placement problem in a power system is given. [ABSTRACT FROM AUTHOR]

Let H be a group and S ⊆ H be a set of group elements such that the identity element e∉S and S = S−1. The Cayley graph Cay(H,S) associated with (H,S) is an undirected graph with a vertex set equal to H and two vertices g,h ∈ H are adjacent, whenever gh−1 ∈ S. Let R be a commutative ring with unity. R+ and Z∗(R) are the additive group and the set of all non-zero zero-divisors of R, respectively. The symbol ℂ픸핐(R) denotes the Cayley graph Cay(R+,Z∗(R)) and GR represents the unitary Cayley graph Cay(R+,U(R)). In this study, the total domination number, perfect domination number and bondage number for ℂ픸핐(R) and GR have been found. Moreover, we establish the relationship between the total domination number of GR and the number of prime ideals in R. Additionally, we identify all finite commutative rings with unity R where the perfect domination number of ℂ픸핐(R) is equal to |R|. [ABSTRACT FROM AUTHOR]

Let G be a graph and S ⊆ V (G). If S is a dominating set of G, and for each vertex u ∈ V (G) − S , there is a neighbor of u in S , denoted by v , such that (S ∖ { v }) ∪ { u } is a dominating set of G , then S is a secure dominating set (SDS) of G. Conversely, S is a co-secure dominating set (CSDS) of G if S is a dominating set of G and for each vertex v in S ,   V (G) − S contains a neighbor of v , denoted by u , such that (S ∖ { v }) ∪ { u } is a dominating set of G. The minimum cardinality of a CSDS (resp. SDS) of G is the co-secure (resp. secure) domination number of G. We use γ c s (G) and γ s (G) to denote the co-secure domination number and secure domination number of G , respectively. Arumugam et al. proposed two questions: (1) Characterize a graph G with γ c s (G) = α (G) , where α (G) is the independence number of G ; (2) Characterize a graph G with γ c s (G) = γ s (G). In this paper, we characterize some forbidden induced subgraphs for a graph G with γ c s (G) = α (G) ; moreover, we obtain that γ c s (G) = γ s (G) for each { K 3 , C 5 , P 5 } -free graph G with δ (G) ≥ 2. Our conclusions can generalize some known results. [ABSTRACT FROM AUTHOR]

The main aim of the paper is to give the crossing number of the join product G* + Dn for the graph G* isomorphic to 4-regular graph on six vertices except for two distinct edges with no common vertex such that two remaining vertices are still adjacent, and where Dn consists of n isolated vertices. The proofs are done with the help of well-known exact values for crossing numbers of join products of four subgraphs Hk of G* with discrete graphs. Further, we give a conjecture concerning crossing numbers of the join products of Dn with Wm\e for both types edges e of wheels Wm of m + 1 vertices. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a graph with vertex set V and edge set E. A subset D of V is called a dominating set of G if for any v in V − D , there exists a vertex u ∈ D such that u and v are adjacent. The minimum cardinality of a dominating set of G is called the domination number of G and is denoted by γ (G). Several domination parameters have been introduced. Among them, point set domination was conceived by Sampathkumar and Pushpa Latha [E. Sampathkumar and L. Pushpa Latha, Point-set domination number of a graph, Indian J. Pure Appl. Math.24(4) (1993) 225–229]. A subset D of V (G) is called a point set dominating set of G if for every subset T of V − D , there exists a vertex u ∈ D such that T ∪ { u } is connected in G. The minimum cardinality of a point set dominating set of G is called the point set domination number of G and is denoted by γ p (G). Kulli [V. R. Kulli, The Maximal Domination Number of a Graph, Graph Theory Notes of New York XXXIII (Academy of Sciences, 1997), pp. 11–13] introduced the concept of maximal domination number in a graph. A subset D of V (G) is called a maximal dominating set of G if D is a dominating set of G and V − D is not a dominating set of G. The minimum cardinality of a maximal dominating set of G is denoted by γ m (G). In this paper, the concept of maximal domination is combined with point set domination and maximal point set domination is studied. [ABSTRACT FROM AUTHOR]

For a graph G , let i k (G) be the number of independent sets of size k in G. The independence polynomial I (G ; x) = ∑ k ≥ 0 i k (G) x k has been the focus of considerable research. In this paper, using the coefficients of independence polynomials, we order graphs with some given parameters. We first determine the extremal graph whose all coefficients of I (G ; x) are the largest (respectively, smallest) among all connected graphs (respectively, bipartite graphs) with given vertex cover number. Then we also derive the extremal graph whose all coefficients of I (G ; x) are the largest among all connected graphs (respectively, bipartite graphs) with given vertex dominate number. [ABSTRACT FROM AUTHOR]

Wireless Power Transfer technology, which can charge IoT devices over the air, has become a promising technology for IoT networks. In wireless-powered IoT networks, broadcasting is a fundamental networking service for disseminating messages to the whole network. To seek a fast and collision-free broadcast schedule, the problem of Minimum Latency Broadcast Scheduling (MLBS) has been well studied when nodes are energy-abundant. However, in wireless-powered networks, a node can only receive or transmit packets after it has harvested enough energy. In such networks, it is of great importance to exploit the divergent harvested energy to reduce the broadcast latency. Unfortunately, existing works always assume a predetermined tree and a fixed transmission power for broadcast scheduling, which greatly limits their performance. Thus, in this article, we investigate the first work for the MLBS problem in wireless-powered networks without relying on predetermined trees. First, the problem is formulated and proved to be NP-hard. Then, two structure-adaptive scheduling algorithms are proposed with a theoretical bound, which can intertwine the construction of broadcast tree with the computation of an energy-aware schedule simultaneously. Furthermore, a power-aware scheduling method is also proposed to take the structure of the broadcast tree, the adjustment of nodes' transmission powers, and the interference during transmissions into account simultaneously. Additionally, the algorithm for the MLBS problem under the physical interference model is also studied. Finally, the theoretical analysis and simulation results verify that the proposed algorithms have high performance in terms of latency. [ABSTRACT FROM AUTHOR]

Consider a graph G = (V , E) and a function f : V → { 0 , 1 , 2 }. A vertex u with f (u) = 0 is defined as undefended by f if it lacks adjacency to any vertex with a positive f -value. The function f is said to be a weak Roman dominating function (WRD function) if, for every vertex u with f (u) = 0 , there exists a neighbor v of u with f (v) > 0 and a new function f ′ : V → { 0 , 1 , 2 } defined in the following way: f ′ (u) = 1 , f ′ (v) = f (v) − 1 , and f ′ (w) = f (w) , for all vertices w in V ∖ { u , v } ; so that no vertices are undefended by f ′. The total weight of f is equal to ∑ v ∈ V f (v) , and is denoted as w (f). The Weak Roman domination number denoted by γ r (G) , represents m i n { w (f) | f is a WRD function of G }. For a given graph G , the problem of finding a WRD function of weight γ r (G) is defined as the Minimum Weak Roman domination problem. The problem is already known to be NP-hard for bipartite and chordal graphs. In this paper, we further study the algorithmic complexity of the problem. We prove the NP-hardness of the problem for star convex bipartite graphs and comb convex bipartite graphs, which are subclasses of bipartite graphs. In addition, we show that for the bounded degree star convex bipartite graphs, the problem is efficiently solvable. We also prove the NP-hardness of the problem for split graphs, a subclass of chordal graphs. On the positive side, we present a polynomial-time algorithm to solve the problem for P 4 -sparse graphs. Further, we have presented some approximation results. [ABSTRACT FROM AUTHOR]

A path in a total-colored graph G is called a total-rainbow path if its edges and internal vertices have distinct colors. The total-colored graph G is total-rainbow connected if for any two distinct vertices of G , there is a total-rainbow path connecting them. The total-rainbow connection number of G , denoted as t r c (G) , represents the minimum number of colors that are required to make G total-rainbow connected. This paper characterizes all the families F of connected graphs with | F | ∈ { 1 , 2 } , for which there exists a constant k F such that G being a connected F -free graph implies t r c (G) ≤ 2 d i a m (G) + k F , where d i a m (G) denotes the diameter of G. [ABSTRACT FROM AUTHOR]

An outer-independent triple Roman dominating function (OI[3]RDF) on a graph G = (V,E) is function f : V →{0, 1, 2, 3, 4} having the property that (i) if f(v) = 0, then v must have either a neighbor assigned 4 or two neighbors one of which is assigned 3 and the other at least 2 or v has three neighbors all assigned 2; (ii) no two vertices assigned 0 are adjacent; (iii) if f(v) = 1, then v must have either a neighbor assigned at least 3 or two neighbors assigned 2; (iv) if f(v) = 2, then v must have one neighbor assigned at least 2. The weight of an OI[3]RDF is the sum of its function value over the whole set of vertices, and the outer-independent triple Roman domination number of G is the minimum weight of an OI[3]RDF on G. In this paper, we continue the study of outer-independent triple Roman domination number of graphs by first presenting two sharp lower bounds for the outer-independent triple Roman domination number of trees. Then we strengthen the NP-complete result of the outer-independent triple Roman domination problem for bipartite graphs by showing that the problem remains NP-complete for a subclass of bipartite graphs, namely tree convex bipartite graphs, where two special trees are considered. [ABSTRACT FROM AUTHOR]

A set D of vertices of a simple graph G = (V,E) is a strong dominating set, if for every vertex x ∈D¯ = V ∖D there is a vertex y ∈ D with xy ∈ E(G) and deg(x) ≤deg(y). The strong domination number γst(G) is defined as the minimum cardinality of a strong dominating set. The strong domatic number dst(G) is the maximum number of strong dominating sets into which the vertex set of G can be partitioned. We initiate the study of the strong domatic number, and we present different sharp bounds on dst(G). In addition, we determine this parameter for some classes of graphs such as cubic graphs of order at most 10. [ABSTRACT FROM AUTHOR]

AbstractLet (R,m) be a Noetherian normal local domain with m as the maximal ideal. To this ring R, we assign a simple undirected graph RSG(R) which we call as a regular sequence graph of R. The vertices, V(RSG(R)), of this graph are distinct non-zero elements of m and two vertices x, y are adjacent if and only if {x,y} forms a R-regular sequence. In this paper, we show that the RSG(R) is connected, Hausdorff, and it has an infinite clique. Moreover we show that the regular sequence graph RSG(R) is compact if and only if the class group Cl(R) is torsion. [ABSTRACT FROM AUTHOR]

A perfect Roman {3}‐dominating function on a graph G = (V, E) is a function f : V⟶{0, 1, 2, 3} having the property that if f(v) = 0, then ∑u∈N(v)f(u) = 3, and if f(v) = 1, then ∑u∈N(v)f(u) = 2 for any vertex v ∈ V. The weight of a perfect Roman {3}‐dominating function f is the sum ∑v∈Vf(v). The perfect Roman {3}‐domination number of a graph G, denoted by γR3pG, is the minimum weight of a perfect Roman {3}‐dominating function on G. In this paper, we initiate the study of a perfect Roman {3}‐domination, and we show that the decision problem associated with a perfect Roman {3}‐domination is NP‐complete for bipartite graphs. We also prove that if T is a tree of order n ≥ 2, then γR3pT≤32n/ and characterize trees achieving this bound, and we give an infinity set of trees T of order n for which γR3pT approaches this bound as n goes to infinity. Finally, we give the best upper bound of γR3pG for some classes of graphs including regular, planar, and split graphs in terms of the order of the graphs. [ABSTRACT FROM AUTHOR]

A set S of vertices in a graph G is a dominating set if every vertex not in S is adjacent to a vertex in S. If, in addition, S is an independent set, then S is an independent dominating set, while if every vertex of the dominating set S is adjacent to a vertex in S , then S is a total dominating set of G. A fundamental problem in domination theory in graphs is to determine which graphs have the property that their vertex set can be partitioned into two types of dominating sets. In particular, we are interested in graphs whose vertex set can be partitioned into a total dominating set and an independent dominating set. In this paper, we solve this problem by providing a constructive characterization of such graphs. We show that all such graphs can be constructed starting from two base graphs and applying a sequence of eleven operations. [ABSTRACT FROM AUTHOR]

Given a graph G without isolated vertices, a function f : V (G) → { 0 , 1 , 2 } is a covering total Italian dominating function if (i) the set of vertices labeled with 0 forms an independent set; (ii) every vertex labeled with 0 is adjacent to two vertices labeled with 1 or to one vertex labeled with 2; and (iii) the set of vertices labeled with 1 or 2 forms a total dominating set. The covering total Italian domination number of G is the smallest possible value of the sum ∑ v ∈ V (G) f (v) among all possible covering total Italian dominating functions f on V (G). The concepts above are introduced in this article, and the study of its combinatorial and computational properties is initiated. Specifically, we show several relationships between such parameter and other domination related parameters in graphs. We also prove the NP-completeness of the related decision problem for bipartite graphs, and present some approximation results on computing our parameter. In addition, we compute the exact value of the covering total Italian domination number of some graphs with emphasis on some Cartesian products. [ABSTRACT FROM AUTHOR]

Let G be a finite group with the identity e and S be a subset of G ∖︀ { e } such that S = S − 1 . Let m be an integer such that 2 ≤ m ≤ max { o (s) ∣ s ∈ S } , where o (s) is the order of s in G. The m -Cayley hypergraph H of G over S , m - Cay (G , S) , is a hypergraph with vertex set G and an edge set { { s i x ∣ 0 ≤ i ≤ m − 1 } ∣ x ∈ G , s ∈ S }. We discover a necessary and sufficient condition for a subset S of G ∖︀ { e } such that a subgroup H is a perfect code in m - Cay (G , S) and obtain some conditions for a subgroup H that guarantee the existence of a subset S ⊆ G ∖︀ { e } such that H is a perfect code in m - Cay (G , S). [ABSTRACT FROM AUTHOR]

For a given graph G = (V,E), a Roman {3}-dominating function or double Italian dominating function (abbreviated DIDF) is a function f : V →{0, 1, 2, 3} which satisfies the following condition: ∀u ∈ V, f(u) ∈{0, 1}⇒ f(N[u]) ≥ 3. The weight of a Roman {3}-dominating function or double Italian dominating function is the sum wf = Σv∈V (G)f(v) and the minimum weight of a Roman {3}-dominating function f is the Roman {3}-domination number or double Italian domination number, denoted by γR3(G) or γdI(G). A perfect double Italian dominating function (abbreviated PDIDF) is a double Italian dominating function such that if f(u) ∈{0, 1} then 3 ≤ Σv∈N[u]f(v) ≤ 4, where N(u) is the set of vertices adjacent to u and N[u] = N(u) ∪{u}. The minimum weight of a perfect double Italian dominating function on G is the perfect double Italian domination number of G, denoted by γdIP(G). In this paper, we find that γdI(S(Cn, 2)) = γdIP(S(C n, 2)) = n(n − 1) for n ≥ 6, where S(G,t) is generalized Sierpiński graph. A comparison between γdI(G) and γdR(G) is assessed. Further γdI(S(G, 2)) and γdIP(S(G, 2)) is found when G is a graph with a single universal vertex and when G is a graph having at least two universal vertices. We have examined a class of graphs for which γdIP(S(G, 2)) = 3n − 1, provided G has a single universal vertex. [ABSTRACT FROM AUTHOR]

Let G = (V,E) be a simple graph. A dominating set of G is a subset S ⊆ V such that every vertex not in S is adjacent to at least one vertex in S. The cardinality of a smallest dominating set of G, denoted by γ(G), is the domination number of G. A dominating set S is called a super dominating set of G, if for every vertex u ∈S¯ = V ∖S, there exists v ∈ S such that N(v)∩S¯ = {u}. The cardinality of a smallest super dominating set of G, denoted by γsp(G), is the super domination number of G. In this paper, we obtain more results on the super domination number of graphs which is modified by an operation on vertices. Also, we present some sharp bounds for super domination number of chain and bouquet of pairwise disjoint connected graphs. [ABSTRACT FROM AUTHOR]

In this paper, we consider the connected power domination number (γP,c) of three standard products of graphs. The exact value of the connected power domination number of G ∘ H is obtained for any two nontrivial graphs G and H. Further, tight upper bounds are proved for the connected power domination number of the Cartesian product of two graphs G and H. Consequently, the exact value of the connected power domination number of the Cartesian product of some standard graphs is determined. Finally, the connected power domination number of the tensor product of graphs is discussed. [ABSTRACT FROM AUTHOR]

A set S of vertices in a graph G is said to be a unique strong isolate semitotal dominating set of G if it is an isolated dominating set of G in which there exists exactly one vertex v ∈ D such that N2(v) ∩D = Φ, where N2(v) = {x/d(x, v) ≤2 and x ≠ v} and N2(u) ∩D≠ Φ for every u(≠ v) ∈ D and |D-{v}| > 1. In this paper, we obtained some bounds for USISTD-set. Further, we studied some basic properties of USISTD-set. Also the USISTD number for disconnected graphs are obtained. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a graph and k be an integer representing k colors. There is a function f from V to the power set of k colors satisfying every vertex v ∈ V assigned ∅ under f in its neighborhood has all the colors, then f is called a k -rainbow dominating function (k RDF) on G. The weight of f is the sum of the number of colors on each vertex all over the graph. The k -rainbow domination number of G is the minimum weight of k RDFs on G , denoted by γ r k (G). The aim of this paper is to investigate the k -rainbow (k = 3 , 4) domination number of the Cartesian product of paths P m □ P n and the Cartesian product of paths and cycles P m □ C n . For P m □ P n , we determine the value γ r 3 (P 4 □ P n) = 2 n + 2 and present γ r 3 (P m □ P n) ≤ m n 2 + 2 for m ≥ 5. For P m □ C n , we determine the values of γ r 3 (P m □ C n) for m = 3 , 4 or n = 3 , 4 and γ r 4 (P m □ C n) for m = 3 or n = 3. [ABSTRACT FROM AUTHOR]

We describe a simple deterministic O (ε - 1 log Δ) round distributed algorithm for (2 α + 1) (1 + ε) approximation of minimum weighted dominating set on graphs with arboricity at most α . Here Δ denotes the maximum degree. We also show a lower bound proving that this round complexity is nearly optimal even for the unweighted case, via a reduction from the celebrated KMW lower bound on distributed vertex cover approximation (Kuhn et al. in JACM 63:116, 2016). Our algorithm improves on all the previous results (that work only for unweighted graphs) including a randomized O (α 2) approximation in O (log n) rounds (Lenzen et al. in International symposium on distributed computing, Springer, 2010), a deterministic O (α log Δ) approximation in O (log Δ) rounds (Lenzen et al. in international symposium on distributed computing, Springer, 2010), a deterministic O (α) approximation in O (log 2 Δ) rounds (implicit in Bansal et al. in Inform Process Lett 122:21–24, 2017; Proceeding 17th symposium on discrete algorithms (SODA), 2006), and a randomized O (α) approximation in O (α log n) rounds (Morgan et al. in 35th International symposiumon distributed computing, 2021). We also provide a randomized O (α log Δ) round distributed algorithm that sharpens the approximation factor to α (1 + o (1)) . If each node is restricted to do polynomial-time computations, our approximation factor is tight in the first order as it is NP-hard to achieve α - 1 - ε approximation (Bansal et al. in Inform Process Lett 122:21-24, 2017). [ABSTRACT FROM AUTHOR]

In graph theory, the neutrosophic graph is a new extension of the intuitionistic fuzzy graph and fuzzy graph. It offers greater accuracy and flexibility in scheduling and implementing numerous real-life issues. The introduction of neutrosophic graphs has opened up an excellent opportunity to portray real-world situations with incomplete and ambiguous information. These neutrosophic graph models are used in many industrial and scientific domains to simulate various problems. This article offers a new approach for calculating the total dominating set of a given single-valued neutrosophic graph using neutrosophic strong arcs. An example is illustrated for calculating the total dominating sets of single-valued neutrosophic graphs. Moreover, certain observations related to uniform single-valued neutrosophic graphs are covered and we also suggest an application of a total dominating set in single-valued neutrosophic graphs in the real world. [ABSTRACT FROM AUTHOR]

A bipartite graph G(X, Y) is called a star-convex bipartite graph with convexity on X if there is an associated star T(X, F), such that for each vertex in Y, its neighborhood in X induces a subtree in T. A graph G is said to be a split graph if G can be partitioned into a clique (K) and an independent set (I). The objective of this study is twofold: (i) to strengthen the complexity results presented in Chen et al. (J Comb Optim 32(1):95–110, 2016) for the Hamiltonian cycle (HCYCLE), the Hamiltonian path (HPATH), and the Domination (DS) problems on star-convex bipartite graphs (ii) to reinforce the results of Müller (Discret Math 156(1–3):291–298, 1996) for HCYCLE, and HPATH on split graphs by introducing a convex ordering on one of the partitions (K or I). As part of our fine-grained analysis study with the diameter being the parameter, we first show that the diameter of star-convex bipartite graphs is at most six. Next, we observe that the reduction instances of Chen et al. (J Comb Optim 32(1):95–110, 2016) are star-convex bipartite graphs with at most diameter 4, and hence HCYCLE and HPATH are NP-complete on star-convex bipartite graphs with at most diameter 4. We strengthen this result and establish the following results on star-convex bipartite graphs: (i) HCYCLE is NP-complete for diameter 3, and polynomial-time solvable for diameters 2, 5, and 6 (a transformation in complexity: P to NPC to P) (ii) HPATH is polynomial-time solvable for diameter 2, and NP-Complete, otherwise (a dichotomy). Further, with convexity being the parameter, for split graphs with convexity on K (resp. I), we show that HCYCLE and HPATH are NP-complete on star-convex (resp. comb) split graphs with convexity on K (resp. I). Further, we show that HCYCLE is NP-complete on k 1 , r -free star-convex split graphs with convexity on I, r ≥ 6 . On the positive side, we show that for K 1 , 5 -free star-convex split graphs with convexity on I, HCYCLE is polynomial-time solvable. Thus, we establish a dichotomy for HCYCLE on star-convex split graphs with convexity on I. We further show that the dominating set problem (DS) and its variants (resp. Connected, Total, Outer-Connected, and Dominating biclique) are NP-complete on star-convex bipartite graphs with diameter 3 (resp. diameter 5, and diameter 6). On the parameterized complexity front, we prove that the parameterized version of the domination problem and its variants, with the parameter being the solution size, is not fixed-parameter tractable for star-convex bipartite graphs with diameter 3 (resp. diameter 5, and diameter 6), whereas it is fixed-parameter tractable when the parameter is the number of leaves in the associated star. Further, we show that for star-convex bipartite graphs with diameters 5, and 6, the domination problem and its variants cannot be approximated within (1 - ϵ) ln n unless NP ⊆ T I M E (2 n o (1) ) . [ABSTRACT FROM AUTHOR]

The goal of systems biology is to gain a network level understanding of how gene interactions influence biological states, and ultimately inform upon human disease. Given the scale and scope of systems biology studies, resource constraints often limit researchers when validating genome-wide phenomena and potentially lead to an incomplete understanding of the underlying mechanisms. Further, prioritization strategies are often biased towards known entities (e.g. previously studied genes/proteins with commercially available reagents), and other technical issues that limit experimental breadth. Here, heterogeneous biological information is modeled as an association graph to which a high-performance minimum dominating set solver is applied to maximize coverage across the graph, and thus increase the breadth of experimentation. First, we tested our model on retrieval of existing gene functional annotations and demonstrated that minimum dominating set returns more diverse terms when compared to other computational methods. Next, we utilized our heterogenous network and minimum dominating set solver to assist in the process of identifying understudied genes to be interrogated by the International Mouse Phenotyping Consortium. Using an unbiased algorithmic strategy, poorly studied genes are prioritized from the remaining thousands of genes yet to be characterized. This method is tunable and extensible with the potential to incorporate additional user-defined prioritizing information. The minimum dominating set approach can be applied to any biological network in order to identify a tractable subset of features to test experimentally or to assist in prioritizing candidate genes associated with human disease. [ABSTRACT FROM AUTHOR]

Wireless Sensor Networks (WSNs) play a significant role in monitoring changes in the physical environment, relying on a subset of designated nodes known as the Connected Dominating Set (CDS) to facilitate communication and serve as the network's virtual backbone for routing and clustering. Despite the various algorithms for CDS construction, the challenges persist in terms of construction cost and scalability. In this context, this paper introduces the utilisation of the Hunger Games Search Optimisation Algorithm (HGSOA) for Connected Dominating Set Construction in Wireless Sensor Networks (HGSOA-CDS-WSN). The primary intention of this paper is "to develop a technique capable of constructing small-sized CDS with reduced construction costs, particularly suitable for uniformly or randomly distributed nodes". The proposed HGSOA-CDS-WSN method is implemented in MATLAB based on various metrics. The results are compared with those of existing techniques, such as the Parallel Structure from Motion for UAV Pictures using Weighted CDS (PSfM-CDS-WSN), Polyhedra Associated with Locating-Dominating, Open Locating-Dominating, and Locating Total-Dominating Sets in Graphs (PAL-CDS-WSN), and Sustainable Maintenance of Connected Dominating Set by Solar Energy Harvesting for Internet of Things Networks (SHE-CDS-WSN). The proposed technique achieves lower delay by 13.24%, 25.64%, and 9.96%, and higher throughput by 18.34%, 24.55%, and 23.04% compared to the existing methods. This systematic evaluation underscores the efficacy and superiority of the proposed HGSOA-CDS-WSN technique in terms of connected dominating set size, construction time, energy efficiency, network stability, and overall performance, highlighting its potential to advance wireless sensor network applications. [ABSTRACT FROM AUTHOR]

Let G be a graph with vertex set V. A function f : V → { − 1 , 0 , 2 } is called a Roman balanced dominating function (RBDF) of G if ∑ u ∈ N G [ v ] f (u) = 0 for each vertex v ∈ V. The maximum (resp. minimum) Roman balanced domination number γ R b M (G) (resp. γ R b m (G)) is the maximum (resp. minimum) value of ∑ v ∈ V f (v) among all Roman balanced dominating functions f. A graph G is called R d -balanced if γ R b M (G) = γ R b m (G) = 0. In this paper, we obtain several upper and lower bounds on γ R b M (G) and γ R b m (G) and further determine several classes of R d -balanced graphs. [ABSTRACT FROM AUTHOR]

The rise of the Internet of Things (IoT) has generated significant interest by enabling connectivity across various objects, ranging from the smallest devices to large-scale systems. Despite its benefits, IoT poses considerable security challenges due to the many interconnected devices that collect and transmit sensitive data across networks. Therefore, ensuring robust data protection and preventing unauthorized access or misuse are essential concerns. To address this issue, strategically placing security services within IoT networks is vital for safeguarding both devices and data. One promising strategy for optimizing this placement is the use of the dominating set concept derived from graph theory, which helps in the efficient allocation of security resources. This study presents an IoT network as a simple weighted graph, considering device capabilities while focusing on adopting the dominating set concept to enhance the placement of security services in IoT networks. To achieve this, an enhanced greedy heuristic is proposed for efficiently generating the dominating set. The effectiveness and performance of the proposed approach are evaluated through a comparative analysis combined with existing methods in the recent literature. [ABSTRACT FROM AUTHOR]

Copyright of Operations Research Transactions / Yunchouxue Xuebao is the property of Editorial office of Operations Research Transactions and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Domination in graphs has been an extensively researched branch of graph theory. A set S ∊ V is said to be the dominating set of graph G if for every v ∊ V - S there exists a vertex u ∊ S such that uv ∊ E. The minimum cardinality of vertices among the dominating set of G is called the domination number of G denoted by γ(G) The main object of this paper is to study the domination number of some networks such as triangular belt networks TB(n), alternate triangular belt networks ATB(n) and restricted square of bistar networks Bn,n. [ABSTRACT FROM AUTHOR]

We address in this paper a variant of the scheduling-location (ScheLoc) problem on tree networks with interval edge lengths where the total deviation of the uncertain data cannot exceed a threshold. We further use the minmax regret concept to deal with the corresponding uncertainty. In order to solve the problem, we investigate the structure of the schedule which leads to the maximum regret value at a fixed point. Then we consider the machine location belonging to a specific edge of the tree and partition the underlying edge into regions with linear maximum regret function. Finally, we develop a combinatorial algorithm that solves the minmax regret ScheLoc problem in polynomial time based on a finite dominating set approach. [ABSTRACT FROM AUTHOR]

The minimum weight connected dominating set problem in wireless sensor networks plays an important role in many applications such as backbone construction, routing, and scheduling. In wireless sensor networks, where each node has a weight, this paper proposes an optimization algorithm that divides the entire network into small groups and minimizes the total weights of the dominator that serves as the header of each group. The proposed optimization algorithm applies a meta-heuristic tabu search algorithm to solve the given problem. The proposed tabu search algorithm is designed to minimize the total weight of the dominator by proposing an efficient encoding structure and neighborhood generation methods. The performance evaluation of the proposed tabu search algorithm is carried out in terms of the total weights of all available dominators and execution time in various network environments in networks with a large number of nodes. The evaluation results show that the proposed tabu search algorithm outperforms the existing optimization algorithms by about 10-20%. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Hyperstructures is the property of University of Mohaghegh Ardabili and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

The article draws on insights from the literature on street‐level bureaucracy to analyze how public officials experience and deal with challenges arising from hybrid governance. Empirically, we focus on managerial staff and front‐line workers employed in Danish employment service delivery organizations, respectively. We develop the term "ignoring by complying" to describe how informants pursue ideals associated with new public governance (NPG) in settings dominated by more than one governance logic. They comply with the minimum standards associated with the logics of public administration (PA) and new public management (NPM) in order to ignore such logics most of the time. The article thereby contributes to the growing bodies of literature on cross‐pressures in public bureaucracies, particularly by putting recent street‐level bureaucracy research in touch with literature on hybrid governance. [ABSTRACT FROM AUTHOR]

Let r ≥ 2. A subset S of vertices of a graph G is a r-hop independent dominating set if every vertex outside S is at distance r from a vertex of S, and for any pair v, w ∈ S, d(v, w) ≠ r. A r-hop Roman dominating function (rHRDF) is a function f on V (G) with values 0, 1 and 2 having the property that for every vertex v ∈ V with f(v) = 0 there is a vertex u with f(u) = 2 and d(u, v) = r. A r-step Roman dominating function (rSRDF) is a function f on V (G) with values 0, 1 and 2 having the property that for every vertex v with f(v) = 0 or 2, there is a vertex u with f(u) = 2 and d(u, v) = r. A rHRDF f is a r-hop Roman independent dominating function if for any pair v, w with non-zero labels under f, d(v, w) ≠ r. We show that the decision problem associated with each of r-hop independent domination, r-hop Roman domination, r-hop Roman independent domination and r-step Roman domination is NP-complete even when restricted to planar bipartite graphs or planar chordal graphs. [ABSTRACT FROM AUTHOR]

Let Γ = (V , E) be a finite undirected graph without loops or multiple edges. A non-empty set of vertices S ⊆ V is called powerful alliance if for every vertex u ∈ N [ S ] , | N [ u ] ∩ S | ≥ | N [ u ] ∩ S ¯ |. A powerful alliance dominating set is called global. The global powerful alliance number γ a p (Γ) is defined as the minimum cardinality among all global powerful alliances. In this paper, we initiate the study of the global powerful alliance number of zero-divisor graphs Γ (R) with R is a finite commutative ring. Hence, we calculate γ a p (Γ (R)) for some usual kind of finite rings. As application, we give the global powerful alliance number of all zero-divisor graphs of finite commutative rings of order ≤ 7. [ABSTRACT FROM AUTHOR]

Let G = (V,E) be a simple connected graph. A dominating set D ⊆ V is an independent dominating set of graph G if the subgraph induced by D is isomorphic to an empty graph. The minimum cardinality of an independent dominating set, denoted by i(G), is called the independent domination number of graph G. It is known that for any tree i(T) ≤ n(T)+γ(T)+l(T) 4. The extremal trees attaining the bound is characterized, which answers the problem posed in [A. Cabrera-Martínez, New bounds on the double domination number of trees, Discrete Appl. Math. 315 (2022) 97–103]. [ABSTRACT FROM AUTHOR]

This article explores Christian principles, imagery, and ideas shaping the (re)making of masculine ideals, behaviour, and identities among Pentecostal Gitanos in Spain. Scholarship on Pentecostal masculinities emphasizes that in cultural settings dominated by ‘macho’ and other chauvinistic principles, men find it challenging to comply with Pentecostal standards of manhood, and those who do convert often lose standing before non‐converted men as they are accorded an aura of effeminacy. Whereas many converted Gitanos struggle to meet Pentecostal moral standards too, Gitano believers attempt to reform their masculinity following dominant and highly valued ethnic ideals. The connection between masculine pathways of conversion, moral/spiritual commitment, and cultural prestige has significant implications for the ways in which Gitano male believers are perceived and appreciated as potential partners in Gitano cultural and communitarian milieus. The article argues that Pentecostal Christianity's gendered ideas about how men should behave defines ideals of masculinity, ethical expectations, and couple‐making practices among Gitano communities. The article also provides an ethnographic account of the mechanisms involved in generating, reproducing, and sustaining discursive, social, and communitarian frameworks and courting practices (known as roneos) in which Pentecostal Gitano ideals and aspirations about manhood become meaningful and appealing. [ABSTRACT FROM AUTHOR]