Search

For a simple undirected connected graph G = (V, E), a maximal Roman dominating function (MRDF) of G is a function f : V (G) → {0, 1, 2} with the following properties: (i) For every vertex v ∈ {v ∈ V|f(v) = 0}, there exists a vertex u ∈ N(v) such that f(u) = 2. (ii) The set {v ∈ V|f(v) = 0} is not a dominating set of G; In other words, there exists a vertex v ∈ {v ∈ V|f(v) ≠ 0} such that N(v) ∩ {u ∈ V|f(u) = 0} ∅. The weight of an MRDF of G is the sum of its function values over all vertices, denoted as f(G) = ∑v∈V (G)f(v), and the maximal Roman domination number of G, denoted by γmR(G), is the minimum weight of an MRDF of G. In this paper, we establish some bounds of the maximal Roman domination number of graphs. Additionally, we develop an integer linear programming formulation to compute the maximal Roman domination number of any graph. Furthermore, we prove that maximal Roman domination problem (MRD) is NP-complete even restricted to star convex bipartite graphs and chordal bipartite graphs. Lastly, we show the maximal Roman domination number of threshold graphs, trees, and block graphs can be computed in linear time. [ABSTRACT FROM AUTHOR]

The star k-edge-coloring of graph G is a proper edge coloring using k colors such that no path or cycle of length four is bichromatic. The minimum number k for which G admits a star k-edge-coloring is called the star chromatic index of G, denoted by χ′s (G). Let GCD(n, k) be the greatest common divisor of n and k. In this paper, we give a necessary and sufficient condition of χ′s (P (n, k)) = 4 for a generalized Petersen graph P (n, k) and show that “almost all” generalized Petersen graphs have a star 5-edge-colorings. Furthermore, for any two integers k and n (≥2k + 1) such that GCD(n, k) ≥ 3, P (n, k) has a star 5-edge-coloring, with the exception of the case that GCD(n, k) = 3, k ≠ GCD(n, k) and n3≡1(mod3){n \over 3} \equiv 1\left( {\bmod 3} \right).

For a simple graph G, the atom–bond connectivity index (ABC) of G is defined as ABC(G) = ∑uv∈ E(G)d(u)+d(v)−2d(u)d(v), $\sum_{uv\in{}E(G)} \sqrt{\frac{d(u)+d(v)-2}{d(u)d(v)}},$where d(v) denotes the degree of vertex v of G. In this paper, we prove that for any bipartite graph G of order n ≥ 6, size 2n − 3 with δ(G) ≥ 2, ABC(G)≤ 2(n−6)+23(n−2)n−3+2, $ABC(G)\leq{}\sqrt{2}(n-6)+2\sqrt{\frac{3(n-2)}{n-3}}+2,$and we characterize all extreme bipartite graphs.

The Sanskruti index of a graph G is defined as S(G)=∑uv∈E(G)sG(u)sG(v)sG(u)+sG(v)−23,$$\begin{align*}S(G)=\sum_{uv\in{}E(G)}{\left(\frac{s_G(u)s_G(v)}{s_G(u)+s_G(v)-2}\right)}^3, \end{align*}$$where sG(u) is the sum of the degrees of the neighbors of a vertex u in G. Let Pn, Cn, Sn and Sn + e be the path, cycle, star and star plus an edge of n vertices, respectively. The Sanskruti index of a molecular graph of a compounds can model the bioactivity of compounds, has a strong correlation with entropy of octane isomers and its prediction power is higher than many existing topological descriptors.

Let G = (V, E) be a graph and let f : V (G) → {0, 1, 2} be a function. A vertex v is said to be protected with respect to f, if f(v) > 0 or f(v) = 0 and v is adjacent to a vertex of positive weight. The function f is a co-Roman dominating function if (i) every vertex in V is protected, and (ii) each v ∈ V with positive weight has a neighbor u ∈ V with f(u) = 0 such that the function fuv : V → {0, 1, 2}, defined by fuv(u) = 1, fuv(v) = f(v) − 1 and fuv(x) = f(x) for x ∈ V \ {v, u}, has no unprotected vertex. The weight of f is ω(f) = ∑v∈V f(v). The co-Roman domination number of a graph G, denoted by γcr(G), is the minimum weight of a co-Roman dominating function on G. In this paper, we give a characterization of graphs of order n for which co-Roman domination number is 2n3${{2n} \over 3}$ or n − 2, which settles two open problem in [S. Arumugam, K. Ebadi and M. Manrique, Co-Roman domination in graphs, Proc. Indian Acad. Sci. Math. Sci. 125 (2015) 1–10]. Furthermore, we present some sharp bounds on the co-Roman domination number.

Based on the uncertainty theory, Liu [B. Liu, Some research problems in uncertainty theory, J. Uncertain Syst. 3 2009, 1, 3–10] introduced an uncertain integral for applying uncertain differential equation, finance, control, filtering and dynamical systems. Since uncertain integrals are the important content of uncertainty theory, this paper explores an approach of the relationship between uncertain integrals by the well-known Chebyshev-type inequality. Also, we propose the concept of an uncertain fractional integral which is generalized version of an uncertain integral. The definition of a strong comonotonic uncertain process and some new properties of the uncertain integral were presented in [C. You and N. Xiang, Some properties of uncertain integral, Iran. J. Fuzzy Syst. 15 2018, 2, 133–142]. Based on the strong comonotonic uncertain process, as an application, we provide Chebyshev's inequality for a fractional uncertain integral and an uncertain integral. [ABSTRACT FROM AUTHOR]

The distance between two vertices u and v in a connected graph G is the number of edges lying in a shortest path (geodesic) between them. A vertex x of G performs the metric identification for a pair (u, v) of vertices in G if and only if the equality between the distances of u and v with x implies that u = v (That is, the distance between u and x is different from the distance between v and x). The minimum number of vertices performing the metric identification for every pair of vertices in G defines themetric dimension of G. In this paper, we performthemetric identification of vertices in two types of polygonal cacti: chain polygonal cactus and star polygonal cactus. [ABSTRACT FROM AUTHOR]

A radio k -labeling of a graph G is an assignment of non-negative integers (labels) to the vertices of G such that the absolute value of the difference between the labels of any two distinct vertices u and v is not less than k + 1 − d (u , v) , where d (u , v) denotes the distance between u and v. The radio k -labeling number of G is the minimum span of a radio k -labeling of G. For a given set of integers D = { d 1 , d 2 , ... , d t } , the distance graph G (Z , D) , denoted also by D (d 1 , d 2 , ... , d t) , has the set of integers Z as its vertex set, while two distinct vertices i , j ∈ Z are adjacent in G (Z , D) if and only if | i − j | ∈ D. Radio k -labelings of three families of distance graphs are considered. Some improved theoretical lower and upper bounds on the radio k -labeling number are presented and some computer-based methods for computing radio k -labelings of these families of graphs are proposed. [ABSTRACT FROM AUTHOR]