Search

A set S of vertices of a connected graph G is a doubly connected dominating set (DCDS) if every vertex not in S is adjacent to some vertex in S and the subgraphs induced by S and V - S are connected. The doubly connected domination number γ cc (G) is the minimum size of such a set. The doubly connected domination subdivision number sd γ cc (G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) to increase the doubly connected domination number. It was conjectured (Karami et al. in Mat Vesnic 64:232–239, 2012) that the doubly connected domination subdivision number of a connected planar graph is at most two. In this paper, we disprove this conjecture by showing that the doubly connected domination subdivision number of the regular icosahedron graph is three. [ABSTRACT FROM AUTHOR]

An outer independent (double) Roman dominating function is a (double) Roman dominating function f for which the set of vertices assigned 0 under f is independent. The outer independent (double) Roman domination number ( γ oidR (G) ) γ oiR (G) is the minimum weight taken over all outer independent (double) Roman dominating functions of G. A vertex cover number β (G) is the minimum size of any vertex cover sets of a graph G. In this work, we present some contributions to the study of outer independent double Roman domination in graphs. Characterizations of the families of all connected graphs with small outer independent double Roman domination numbers, and tight lower and upper bounds on this parameter are given. We also prove that the decision problem associated with γ oidR (G) is NP-complete even when restricted to planar graphs with maximum degree at most four. We moreover prove that 2 β (T) + 1 ≤ γ oidR (T) ≤ 3 β (T) for any tree T, and show that each integer between the lower and upper bounds is realizable. Finally, we give an exact formula for this parameter concerning the corona graphs. [ABSTRACT FROM AUTHOR]

A paired-dominating set of a graph G with no isolated vertex is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number is the minimum cardinality of a paired-dominating set of G. The paired-domination subdivision number is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the paired-domination number. It was conjectured that the paired-domination subdivision number is at most n - 1 for every connected graph G of order n ≥ 3 which does not contain isolated vertices. In this paper, we settle the conjecture in the affirmative. [ABSTRACT FROM AUTHOR]

A double Roman dominating function (DRDF) on a graph G = (V , E) is a function f : V → { 0 , 1 , 2 , 3 } having the property that if f (v) = 0 , then vertex v must have at least two neighbors assigned 2 under f or one neighbor w with f (w) = 3 , and if f (v) = 1 , then vertex v must have at least one neighbor w with f (w) ≥ 2 . The weight of a DRDF is the sum of its function values over all vertices, and the double Roman domination number γ dR (G) is the minimum weight of a DRDF on G. Recently, Khoeilar et al. (Discrete Appl Math 270:159–167, 2019) proved that a connected graph G of order n with minimum degree two different from C 5 and C 7 , satisfies γ dR (G) ≤ 11 10 n. In this paper, we show that this upper bound can be improved to 20 19 n if G is restricted to connected graphs of order n with minimum degree at least two and no C 5 -cycle such that G ∉ { C 7 , C 11 , C 13 , C 17 }. Moreover, we provide an infinite family of graphs attaining this bound. [ABSTRACT FROM AUTHOR]

A Roman dominating function (RD-function) on a graph G = (V, E) is a function f : V → {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. An Roman dominating function f in a graph G is perfect Roman dominating function (PRD-function) if every vertex u with f(u) = 0 is adjacent to exactly one vertex v for which f(v) = 2. The (perfect) Roman domination number γR(G) (γpR(G) γ R p (G) $ {\gamma }_R^p(G)$) is the minimum weight of an (perfect) Roman dominating function on G. We say that γpR(G) γ R p (G) $ {\gamma }_R^p(G)$ strongly equals γR(G), denoted by γpR(G) ≡ γR(G) γ R p (G) ≡ γ R (G) $ {\gamma }_R^p(G)\equiv {\gamma }_R(G)$ , if every RD-function on G of minimum weight is a PRD-function. In this paper we show that for a given graph G, it is NP-hard to decide whether γpR(G) = γR(G) γ R p (G) = γ R (G) $ {\gamma }_R^p(G)={\gamma }_R(G)$ and also we provide a constructive characterization of trees T with γpR(T) ≡ γR(T) γ R p (T) ≡ γ R (T) $ {\gamma }_R^p(T)\equiv {\gamma }_R(T)$. [ABSTRACT FROM AUTHOR]

In this paper, we present a new type of symmetric encryption by converting the classical monoalphabetic affine cipher into a polyalphabetic cipher. The proposed encryption utilizes the properties of outer-convex dominating set in the corona of graphs to generate random keys from the shared keyword to every character of the message. The new encryption eliminates the weaknesses of affine cipher, thus increasing the level of confidence for exchanging messages. [ABSTRACT FROM AUTHOR]

Superior to single-factor authentication, multi-factor authentication (MFA) provides enhanced security by requiring at least two factors to authenticate an entity. It has been studied extensively in recent years and has been applied to various fields. However, there is no adaptive and quantified method to evaluate the dynamic threats coming from different attacks. In this paper, we introduce fuzzy dominating set to model the multiple factors of privacy-preserving identities, and propose an adaptive MFA combinatorial model to achieve adaptive choosing one or multiple privacy-preserving identities to authenticate the user. Moreover, we propose an integer linear programming for solving the Fuzzy Domination Model, and propose a greedy algorithm for Fuzzy Domination (GFD) and a primal dual greedy algorithm for Fuzzy Domination (PDFD) based on this integer linear programming. This work will reduce the gap between dynamic MFA and its practice applications. Finally, the effectiveness and efficiency of both algorithms in MFA are analyzed and experimental results demonstrate that PDFD is comparatively efficient and effective for solving instances with moderate orders. [ABSTRACT FROM AUTHOR]

A double Roman dominating function (DRDF) on a graph G = (V, E) is a function f : V(G) → {0, 1, 2, 3} having the property that if f(v) = 0, then vertex v must have at least two neighbors assigned 2 under f or one neighbor w with f(w) = 3, and if f(v) = 1, then vertex v must have at least one neighbor w with f(w) ≥ 2. A DRDF f is called a global double Roman dominating function (GDRDF) if f is also a DRDF of the complement of G. The weight of a GDRDF is the sum of its function value over all vertices. The global double Roman domination number of G, denoted by γgdR(G), is the minimum weight of a GDRDF on G. In this paper, we initiate the study of the global double Roman domination number. We obtain some properties of global double Roman domination number. [ABSTRACT FROM AUTHOR]

Domination is a structural complexity of chemical molecular graphs. A dominating set in a (molecular) graph G=V,E is a subset S⊆V such that each vertex in V\S is adjacent to at least one vertex in S. The domination number γG of a graph G is the minimum size of a dominating set in G. In this paper, computer-aided approaches for obtaining bounds for domination number on torus graphs are here considered, and many new exact values and bounds are obtained. [ABSTRACT FROM AUTHOR]

In this paper we obtain some bounds and exact values of the total domination numbers and open packing numbers for pyrene torus, hexabenzocoronene, H-phenylenic nanotube and H-napthelenic nanotube. [ABSTRACT FROM AUTHOR]

A signed Roman k -dominating function on a graph G = ( V ( G ) , E ( G ) ) is a function f : V ( G ) → { − 1 , 1 , 2 } such that (i) every vertex u with f ( u ) = − 1 is adjacent to at least one vertex v with f ( v ) = 2 and (ii) ∑ x ∈ N [ w ] f ( x ) ≥ k holds for any vertex w . The weight of f is ∑ u ∈ V ( G ) f ( u ) , the minimum weight of a signed Roman k -dominating function is the signed Roman k -domination number γ s R k ( G ) of G . It is proved that determining the signed Roman k -domination number of a graph is NP-complete for k ∈ { 1 , 2 } . Using a discharging method, the values γ s R 2 ( C 3 □ C n ) and γ s R 2 ( C 4 □ C n ) are determined for all n . [ABSTRACT FROM AUTHOR]

The semitotal domination number of a graph G without isolated vertices is the minimum cardinality of a set S of vertices of G such that every vertex in $$V(G){\setminus } S$$ is adjacent to at least one vertex in S, and every vertex in S is within distance 2 of another vertex of S. In Henning and Marcon (Ann Comb 20(4):1-15, 2016), it was shown that every connected claw-free cubic graph G of order n has semitotal domination number at most $$\frac{4n}{11}$$ when $$n\ge 10$$ , and it was conjectured that the bound can be improved from $$\frac{4n}{11}$$ to $$\frac{n}{3}$$ if $$G\notin \{K_4,N_2\}$$ . In this paper, we prove this conjecture. [ABSTRACT FROM AUTHOR]

A subsetDof the vertex set of a graphGis asecure dominating setofGifDis a dominating set ofGand if, for each vertexunot inD, there is a vertexvinDadjacent tousuch that the swap set (D \{v}) ∪ {u} is again a dominating set ofG. Thesecure domination numberofG, denoted byγs(G), is the cardinality of a smallest secure dominating set ofG. In this paper, we prove that for any treeTonn ≥3 vertices,and the bounds are sharp, whereℓandtare the numbers of leaves and stems ofT, respectively. Moreover, we characterize the treesTsuch that. [ABSTRACT FROM AUTHOR]

For a graph G = (V , E) , an independent Roman dominating function (IRDF) is a function f : V → { 0 , 1 , 2 } having the property that: (1) every vertex assigned a value of 0 is adjacent to at least one vertex assigned a value of 2, (2) there are no two adjacent vertices with positive assignments. The weight of an IRDF ( w (f) ) is the sum of assignments for all vertices. The minimum weight of an independent Roman dominating function on graph G is the independent Roman domination number, denoted by i R (G) . In this paper, we prove that the decision problem of minimum IRDF is N P -complete for chordal bipartite graphs. Then, we research the difference in complexity between the decision problem of RDF and IRDF. Finally, we propose a linear-time algorithm for computing the minimum weight of an independent Roman dominating function in trees. [ABSTRACT FROM AUTHOR]

A double Roman dominating function on a graph G = (V , E) is a function f : V → { 0 , 1 , 2 , 3 } with the properties that if f (u) = 0 , then vertex u is adjacent to at least one vertex assigned 3 or at least two vertices assigned 2, and if f (u) = 1 , then vertex u is adjacent to at least one vertex assigned 2 or 3. The weight of f equals w (f) = ∑ v ∈ V f (v) . The double Roman domination number γ d R (G) of a graph G is the minimum weight of a double Roman dominating function of G. A graph is said to be double Roman if γ d R (G) = 3 γ (G) , where γ (G) is the domination number of G. We obtain the sharp lower bound of the double Roman domination number of generalized Petersen graphs P (3 k , k) , and we construct solutions providing the upper bounds, which gives exact values of the double Roman domination number for all generalized Petersen graphs P (3 k , k) . This implies that P (3 k , k) is a double Roman graph if and only if either k ≡ 0 (mod 3) or k ∈ { 1 , 4 } . [ABSTRACT FROM AUTHOR]

For a simple graph G = (V , E) with no isolated vertices, a total Roman {3}-dominating function(TR3DF) on G is a function f : V (G) → { 0 , 1 , 2 , 3 } having the property that (i) ∑ w ∈ N (v) f (w) ≥ 3 if f (v) = 0 ; (ii) ∑ w ∈ N (v) f (w) ≥ 2 if f (v) = 1 ; and (iii) every vertex v with f (v) ≠ 0 has a neighbor u with f (u) ≠ 0 for every vertex v ∈ V (G) . The weight of a TR3DF f is the sum f (V) = ∑ v ∈ V (G) f (v) and the minimum weight of a total Roman {3}-dominating function on G is called the total Roman {3}-domination number denoted by γ t { R 3 } (G) . In this paper, we show that the total Roman {3}-domination problem is NP-complete for planar graphs and chordal bipartite graphs. Finally, we present a linear-time algorithm to compute the value of γ t { R 3 } for trees. [ABSTRACT FROM AUTHOR]

For a graph G with no isolated vertex, let γ p r (G) and sd γ p r (G) denote the paired-domination and paired-domination subdivision numbers, respectively. In this note, we show that if T is a tree of order n ≥ 4 different from a healthy spider (subdivided star), then sd γ p r (T) ≤ min { γ p r (T) 2 + 1 , n 2 } , improving the (n − 1) -upper bound that was recently proven. [ABSTRACT FROM AUTHOR]

Fuzzy graphs (FGs), broadly known as fuzzy incidence graphs (FIGs), have been acknowledged as being an applicable and well-organized tool to epitomize and solve many multifarious real-world problems in which vague data and information are essential. Owing to unpredictable and unspecified information being an integral component in real-life problems that are often uncertain, it is highly challenging for an expert to illustrate those problems through a fuzzy graph. Therefore, resolving the uncertainty accompanying the unpredictable and unspecified information of any real-world problem can be done by applying a vague incidence graph (VIG), based on which the FGs may not engender satisfactory results. Similarly, VIGs are outstandingly practical tools for analyzing different computer science domains such as networking, clustering, and also other issues such as medical sciences, and traffic planning. Dominating sets (DSs) enjoy practical interest in several areas. In wireless networking, DSs are being used to find efficient routes with ad-hoc mobile networks. They have also been employed in document summarization, and in secure systems designs for electrical grids; consequently, in this paper, we extend the concept of the FIG to the VIG, and show some of its important properties. In particular, we discuss the well-known problems of vague incidence dominating set, valid degree, isolated vertex, vague incidence irredundant set and their cardinalities related to the dominating, etc. Finally, a DS application for VIG to properly manage the COVID-19 testing facility is introduced. [ABSTRACT FROM AUTHOR]

Fuzzy graph models enjoy the ubiquity of being present in nature and man-made structures, such as the dynamic processes in physical, biological, and social systems. As a result of inconsistent and indeterminate information inherent in real-life problems that are often uncertain, for an expert, it is highly difficult to demonstrate those problems through a fuzzy graph. Resolving the uncertainty associated with the inconsistent and indeterminate information of any real-world problem can be done using a vague graph (VG), with which the fuzzy graphs may not generate satisfactory results. The limitations of past definitions in fuzzy graphs have led us to present new definitions in VGs. The objective of this paper is to present certain types of vague graphs (VGs), including strongly irregular (SI), strongly totally irregular (STI), neighborly edge irregular (NEI), and neighborly edge totally irregular vague graphs (NETIVGs), which are introduced for the first time here. Some remarkable properties associated with these new VGs were investigated, and necessary and sufficient conditions under which strongly irregular vague graphs (SIVGs) and highly irregular vague graphs (HIVGs) are equivalent were obtained. The relation among strongly, highly, and neighborly irregular vague graphs was established. A comparative study between NEI and NETIVGs was performed. Different examples are provided to evaluate the validity of the new definitions. A new definition of energy called the Laplacian energy (LE) is presented, and its calculation is shown with some examples. Likewise, we introduce the notions of the adjacency matrix (AM), degree matrix (DM), and Laplacian matrix (LM) of VGs. The lower and upper bounds for the Laplacian energy of a VG are derived. Furthermore, this study discusses the VG energy concept by providing a real-time example. Finally, an application of the proposed concepts is presented to find the most effective person in a hospital. [ABSTRACT FROM AUTHOR]

A dominating set in a graph G is a set of vertices S ⊆ V (G) such that any vertex of V − S is adjacent to at least one vertex of S. A dominating set S of G is said to be a perfect dominating set if each vertex in V − S is adjacent to exactly one vertex in S. The minimum cardinality of a perfect dominating set is the perfect domination number γ p (G). A function f : V (G) → { 0 , 1 , 2 } is a perfect Roman dominating function (PRDF) on G if every vertex u ∈ V for which f (u) = 0 is adjacent to exactly one vertex v for which f (v) = 2 . The weight of a PRDF is the sum of its function values over all vertices, and the minimum weight of a PRDF of G is the perfect Roman domination number γ R p (G). In this paper, we prove that for any nontrivial tree T, γ R p (T) ≥ γ p (T) + 1 and we characterize all trees attaining this bound. [ABSTRACT FROM AUTHOR]

A set S ⊆ V (G) in a graph G is a dominating set if S dominates all vertices in G, where we say a vertex dominates each vertex in its closed neighbourhood. A set is independent if it is pairwise non-adjacent. The minimum cardinality of an independent dominating set on a graph G is called the independent domination number i (G) . A graph G is ID-stable if the independent domination number of G is not changed when any vertex is removed. In this paper, we study basic properties of ID-stable graphs and we characterize all ID-stable trees and unicyclic graphs. In addition, we establish bounds on the order of ID-stable trees. [ABSTRACT FROM AUTHOR]

A double Roman dominating function (DRDF) f on a given graph G is a mapping from V (G) to { 0 , 1 , 2 , 3 } in such a way that a vertex u for which f (u) = 0 has at least a neighbor labeled 3 or two neighbors both labeled 2 and a vertex u for which f (u) = 1 has at least a neighbor labeled 2 or 3. The weight of a DRDF f is the value w (f) = ∑ u ∈ V (G) f (u) . The minimum weight of a DRDF on a graph G is called the double Roman domination number γ d R (G) of G. In this paper, we determine the exact value of the double Roman domination number of the generalized Petersen graphs P (n , 2) by using a discharging approach. [ABSTRACT FROM AUTHOR]

A set D ⊆ V ( G ) of a graph G is a dominating set if every vertex v ∈ V ( G ) is either in D or adjacent to a vertex in D . The domination number γ ( G ) of a graph G is the minimum cardinality of a dominating set of G . Campos and Wakabayashi (2013) and Tokunaga (2013) proved independently that if G is an n -vertex maximal outerplanar graph having t vertices of degree 2, then γ ( G ) ≤ n + t 4 . We improve their upper bound by showing γ ( G ) ≤ n + k 4 , where k is the number of pairs of consecutive 2-degree vertices with distance at least 3 on the outer cycle. Moreover, we prove that γ ( G ) ≤ 5 n 16 for a Hamiltonian maximal planar graph G with n ≥ 7 vertices. [ABSTRACT FROM AUTHOR]