Search

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]

Graphs serve as one of the main tools for the mathematical modeling of various human problems. Fuzzy graphs have the ability to solve uncertain and ambiguous problems. The cubic graph, which has recently gained a position in the fuzzy graph family, has shown good capabilities when faced with problems that cannot be expressed by fuzzy graphs and interval-valued fuzzy graphs. Simultaneous application of fuzzy and interval-valued fuzzy membership indicates a high flexibility in modeling uncertainty issues. The vertex cover is a fundamental issue in graph theory that has wide application in the real world. The previous definition limitations in the vertex covering of fuzzy graphs has directed us to offer new classifications in terms of cubic graph. In this study, we introduced the strong vertex covering and independent vertex covering in a cubic graph with strong edges and described some of its properties. One of the motives of this research was to examine the changes in the strong vertex covering number of a cubic graph if one vertex is omitted. This issue can play a decisive role in covering the graph vertices. Since many of the problems ahead are of hybrid type, by reviewing some operations on the cubic graph we were able to determine the strong vertex covering number on the most important cubic product operations. Finally, two applications of strong vertex covering and strong vertex independence are presented. [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 in natural and human-made structures, namely dynamic process in physical, biological and social systems. As a result of inconsistent and indeterminate information inherent in real-life problems which are often uncertain, it is highly difficult for an expert to model those problems based on a fuzzy graph (FG). Vague graph structure (VGS) can deal with the uncertainty associated with the inconsistent and indeterminate information of any real-world problem, where fuzzy graphs may fail to reveal satisfactory results. Likewise, VGSs are very useful tools for the study of different domains of computer science such as networking, capturing the image, clustering, and also other issues like bioscience, medical science, and traffic plan. The limitations of past definitions in fuzzy graphs have led us to present new definitions in VGSs. Operations are conveniently used in many combinatorial applications. In various situations, they present a suitable construction means; therefore, in this research, three new operations on VGSs, namely, maximal product, rejection, residue product were presented, and some results concerning their degrees and total degrees were introduced. Irregularity definitions have been of high significance in the network heterogeneity study, which have implications in networks found across biology, ecology and economy; so special concepts of irregular VGSs with several key properties were explained. Today one of the most important applications of decision making is in medical science for diagnosing the patient's disease. Hence, we recommend an application of VGS in medical diagnosis. [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]

In recent years, the concept of domination has been the backbone of research activities in graph theory. The application of graphic domination has become widespread in different areas to solve human-life issues, including social media theories, radio channels, commuter train transportation, earth measurement, internet transportation systems, and pharmacy. The purpose of this paper was to generalize the idea of bondage set (BS) and non-bondage set (NBS), bondage number α (G) , and non-bondage number α k (G) , respectively, in the intuitionistic fuzzy graph (IFG). The BS is based on a strong arc (SA) in the fuzzy graph (FG). In this research, a new definition of SA in connection with the strength of connectivity in IFGs was applied. Additionally, the BS, α (G) , NBS, and α k (G) concepts were presented in IFGs. Three different examples were described to show the informative development procedure by applying the idea to IFGs. Considering the examples, some results were developed. Also, the applications were utilized in water supply systems. The present study was conducted to make daily life more useful and productive. [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]

For a graph G = (V , E) with vertex set V = V (G) and edge set E = E (G) , a Roman { 3 } -dominating function (R { 3 } -DF) is a function f : V (G) → { 0 , 1 , 2 , 3 } having the property that ∑ u ∈ N G (v) f (u) ≥ 3 , if f (v) = 0 , and ∑ u ∈ N G (v) f (u) ≥ 2 , if f (v) = 1 for any vertex v ∈ V (G) . The weight of a Roman { 3 } -dominating function f is the sum f (V) = ∑ v ∈ V (G) f (v) and the minimum weight of a Roman { 3 } -dominating function on G is the Roman { 3 } -domination number of G, denoted by γ { R 3 } (G) . Let G be a graph with no isolated vertices. The total Roman { 3 } -dominating function on G is an R { 3 } -DF f on G with the additional property that every vertex v ∈ V with f (v) ≠ 0 has a neighbor w with f (w) ≠ 0 . 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) . We initiate the study of total Roman { 3 } -domination and show its relationship to other domination parameters. We present an upper bound on the total Roman { 3 } -domination number of a connected graph G in terms of the order of G and characterize the graphs attaining this bound. Finally, we investigate the complexity of total Roman { 3 } -domination for bipartite graphs. [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]

The Padmakar–Ivan ( P I ) index is a distance-based topological index and a molecular structure descriptor, which is the sum of the number of vertices over all edges u v of a graph such that these vertices are not equidistant from u and v. In this paper, we explore the results of P I -indices from trees to recursively clustered trees, the k-trees. Exact sharp upper bounds of PI indices on k-trees are obtained by the recursive relationships, and the corresponding extremal graphs are given. In addition, we determine the P I -values on some classes of k-trees and compare them, and our results extend and enrich some known conclusions. [ABSTRACT FROM AUTHOR]

Let γ (D) denote the domination number of a digraph D and let C m □ C n denote the Cartesian product of C m and C n , the directed cycles of length n ≥ m ≥ 3 . Liu et al. obtained the exact values of γ (C m □ C n) for m up to 6 [Domination number of Cartesian products of directed cycles, Inform. Process. Lett. 111 (2010) 36–39]. Shao et al. determined the exact values of γ (C m □ C n) for m = 6 , 7 [On the domination number of Cartesian product of two directed cycles, Journal of Applied Mathematics, Volume 2013, Article ID 619695]. Mollard obtained the exact values of γ (C m □ C n) for m = 3 k + 2 [M. Mollard, On domination of Cartesian product of directed cycles: Results for certain equivalence classes of lengths, Discuss. Math. Graph Theory 33(2) (2013) 387–394.]. In this paper, we extend the current known results on C m □ C n with m up to 21. Moreover, the exact values of γ (C n □ C n) with n up to 31 are determined. [ABSTRACT FROM AUTHOR]

The concept of a metric dimension was proposed to model robot navigation where the places of navigating agents can change among nodes. The metric dimension m d (G) of a graph G is the smallest number k for which G contains a vertex set W, such that | W | = k and every pair of vertices of G possess different distances to at least one vertex in W. In this paper, we demonstrate that m d (H D N 1 (n)) = 4 for n ≥ 2 . This indicates that in these types of hex derived sensor networks, the least number of nodes needed for locating any other node is four. [ABSTRACT FROM AUTHOR]

Given a (molecular) graph, the first multiplicative Zagreb index Π 1 is considered to be the product of squares of the degree of its vertices, while the second multiplicative Zagreb index Π 2 is expressed as the product of endvertex degree of each edge over all edges. We consider a set of graphs G n , k having n vertices and k cut edges, and explore the graphs subject to a number of cut edges. In addition, the maximum and minimum multiplicative Zagreb indices of graphs in G n , k are provided. We also provide these graphs with the largest and smallest Π 1 (G) and Π 2 (G) in G n , k . [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]

Topological indices are numbers related to sub-atomic graphs to allow quantitative structure-movement/property/danger connections. These topological indices correspond to some specific physico-concoction properties such as breaking point, security, strain vitality of chemical compounds. The idea of topological indices were set up in compound graph hypothesis in view of vertex degrees. These indices are valuable in the investigation of mitigating exercises of specific Nanotubes and compound systems. In this paper, we discuss Zagreb types of indices and Zagreb polynomials for a few Nanotubes covered by cycles. [ABSTRACT FROM AUTHOR]

The Cartesian product and join are two classical operations in graphs. Let d L (G) (e) be the degree of a vertex e in line graph L (G) of a graph G. The edge versions of atom-bond connectivity ( A B C e ) and geometric arithmetic ( G A e ) indices of G are defined as ∑ e f ∈ E (L (G)) d L (G) (e) + d L (G) (f) − 2 d L (G) (e) × d L (G) (f) and ∑ e f ∈ E (L (G)) 2 d L (G) (e) × d L (G) (f) d L (G) (e) + d L (G) (f) , respectively. In this paper, A B C e and G A e indices for certain Cartesian product graphs (such as P n □ P m , P n □ C m and P n □ S m ) are obtained. In addition, A B C e and G A e indices of certain join graphs (such as C m + P n + S r , P m + P n + P r , C m + C n + C r and S m + S n + S r ) are deduced. Our results enrich and revise some known results. [ABSTRACT FROM AUTHOR]

The concept of a metric dimension was proposed to model robot navigation where the places of navigating agents can change among nodes. The metric dimension m d ( G ) of a graph G is the smallest number k for which G contains a vertex set W , such that | W | = k and every pair of vertices of G possess different distances to at least one vertex in W . In this paper, we demonstrate that m d ( H D N 1 ( n ) ) = 4 for n ≥ 2 . This indicates that in these types of hex derived sensor networks, the least number of nodes needed for locating any other node is four.

The advances in wireless communication techniques, mobile cloud computing, automotive and intelligent terminal technology are driving the evolution of vehicle ad hoc networks into the Internet of Vehicles (IoV) paradigm. This leads to a change in the vehicle routing problem from a calculation based on static data towards real-time traffic prediction. In this paper, we first address the taxonomy of cloud-assisted IoV from the viewpoint of the service relationship between cloud computing and IoV. Then, we review the traditional traffic prediction approached used by both Vehicle to Infrastructure (V2I) and Vehicle to Vehicle (V2V) communications. On this basis, we propose a mobile crowd sensing technology to support the creation of dynamic route choices for drivers wishing to avoid congestion. Experiments were carried out to verify the proposed approaches. Finally, we discuss the outlook of reliable traffic prediction.