Search

Abstract Let γ r 2 (G) be the 2-rainbow domination number of a graph G. In our work, we solve an open question for 2-rainbow domination number of general Petersen graphs P (n , k). In addition, we proved that γ r 2 (P (n , k)) = n for n ≤ 12 , γ r 2 (P (n , 1)) = n for n ≥ 5 , and γ r 2 (P (2 k + 2 , k)) = 2 k + 2 for k ≥ 2. [ABSTRACT FROM AUTHOR]

Let G be a simple graph. The atom–bond connectivity index ( ABC ) of G is defined as A B C ( G ) = ∑ u v ∈ E ( G ) d ( u ) + d ( v ) − 2 d ( u ) d ( v ) , where d ( v ) denotes the degree of vertex v of G . We characterize the graphs with n vertices, minimum vertex degree  ≥ 2, and m edges for m = 2 n − 4 and m = 2 n − 3 , that have maximum ABC index. [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]

The frequency assignment problem (FAP) asks for assigning frequencies (channels) in a wireless network from the available radio spectrum to the transceivers of the network. One of the graph theoretical models of FAP is the L(3, 2, 1)-labeling of a graph, which is an abstraction of assigning integer frequencies to radio transceivers such that (i) transceivers that are one unit of distance apart receive frequencies that differ by at least three, (ii) transceivers that are two units of distance apart receive frequencies that differ by at least two, and (iii) transceivers that are three units of distance apart receive frequencies that differ by at least one. The relaxation of the L(3, 2, 1)-labeling called the ( s, t, r)-relaxed k- L(3, 2, 1)-labeling is proposed in this paper. This concept is a generalization of the ( s, t)-relaxed k- L(2, 1)-labeling (Lin in J Comb Optim 2016, doi:). Basic properties of ( s, t, r)-relaxed k- L(3, 2, 1)-labeling are discussed and optimal ( s, t, r)-relaxed k- L(3, 2, 1)-labelings for paths and some cycles as well as for the hexagonal lattice and the square lattice are determined. [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]

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]

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]

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]

Abstract An edge metric generator of a connected graph G is a vertex subset S for which every two distinct edges of G have distinct distance to some vertex of S , where the distance between a vertex v and an edge e is defined as the minimum of distances between v and the two endpoints of e in G. The smallest cardinality of an edge metric generator of G is the edge metric dimension, denoted by dim e (G). It follows that 1 ≤ dim e (G) ≤ n − 1 for any n -vertex graph G. A graph whose edge metric dimension achieves the upper bound is topful. In this paper, the structure of topful graphs is characterized, and many necessary and sufficient conditions for a graph to be topful are obtained. Using these results we design an O (n 3) time algorithm which determines whether a graph of order n is topful or not. Moreover, we describe and address an interesting class of topful graphs whose super graphs obtained by adding one edge are not topful. [ABSTRACT FROM AUTHOR]