Search

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 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]

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]

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]