Search

Let k ≥ 1 be an integer and G be a simple and finite graph with vertex set V (G). A signed total Roman k -dominating function (STR k DF) on a graph G is a function f : V (G) → { − 1 , 1 , 2 } such that (i) every vertex v with f (v) = − 1 is adjacent to at least one vertex u with f (u) = 2 and (ii)  ∑ u ∈ N (v) f (u) ≥ k holds for any vertex v. The weight of an STR k DF f is ∑ u ∈ V (G) f (u) , and the minimum weight of an STR k DF is the signed total Roman k -domination number γ stR k (G) of G. In this paper, we establish some sharp bounds on the signed total Roman 2-domination number. [ABSTRACT FROM AUTHOR]

Let k ≥ 1 be an integer and G be a simple and finite graph with vertex set V(G). A signed double Roman k-dominating function (SDRkDF) on a graph G is a function f:V(G) → {−1,1,2,3} such that (i) every vertex v with f(v) = −1 is adjacent to at least two vertices assigned a 2 or to at least one vertex w with f(w) = 3, (ii) every vertex v with f(v) = 1 is adjacent to at least one vertex w with f(w) ≥ 2 and (iii) ∑u∈N[v]f(u) ≥ k holds for any vertex v. The weight of a SDRkDF f is ∑u∈V(G)f(u), and the minimum weight of a SDRkDF is the signed double Roman k-domination number γksdR(G) γ sdR k (G) $ {\gamma }_{{sdR}}^k(G)$ of G. In this paper, we investigate the signed double Roman k-domination number of trees. In particular, we present lower and upper bounds on γksdR(T) γ sdR k (T) $ {\gamma }_{{sdR}}^k(T)$ for 2 ≤ k ≤ 6 and classify all extremal trees. [ABSTRACT FROM AUTHOR]

Given a positive integer t and a graph F, the goal is to assign a subset of the color set { 1 , 2 , ... , t } to every vertex of F such that every vertex with the empty set assigned has all t colors in its neighborhood. Such an assignment is called the t-rainbow dominating function ( t RDF ) of the graph F. A t RDF is independent ( I t RDF ) if vertices assigned with non-empty sets are pairwise non-adjacent. The weight of a t RDF g of a graph F is the value w (g) = ∑ v ∈ V (F) | g (v) | . The independent t-rainbow domination number i r t (F) is the minimum weight over all I t RDF s of F. In this article, it is proved that the independent t-rainbow domination problem is NP-complete even if the input graph is restricted to a bipartite graph or a planar graph, and the results of the study provide some bounds for the independent t-rainbow domination number of any graph for a positive integer t. Moreover, the exact values and bounds of the independent t-rainbow domination numbers of some Petersen graphs and torus graphs are given. [ABSTRACT FROM AUTHOR]

A set S⊆V(G) is a k-distance independent set of a graph G if the distance between every two vertices of S is greater than k. The k-distance independence number αk(G) of G is the maximum cardinality over all k-distance independent sets in G. A k-distance coloring of G is a function f from V(G) onto a set of positive integers (colors) such that for any two distinct vertices u and v at distance less than or equal to k we have f(u)≠f(v). The k-distance chromatic number of a graph G is the smallest number of colors needed to have a k-distance coloring of G. The k-distance independence numbers and 2-distance chromatic numbers of Cartesian products of cycles are considered. A computer-aided method with the isomorphic rejection is used to determine the k-distance independence numbers of Cartesian products of cycles. By using these results, several lower and upper bounds on the maximal cardinality AqL(n,d) of a q-ary Lee code of length n with a minimum distance at least d are improved. It is also established that the 2-distance chromatic number of G equals |V(G)|α(G2) for G=Cm□Cn□Ck, whenever k≥3 and (m,n)∈{(3,3),(3,4),(3,5),(4,4)} or k, m and n are all multiples of seven. Moreover, it is shown that the 2-distance chromatic number of the three-dimensional square lattice is equal to seven. [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]

A graphGis uniquelyk-colourable if the chromatic number ofGiskandGhas only onek-colouring up to permutation of the colours. Aksionov [On uniquely 3-colorable planar graphs, Discrete Math. 20 (1977), pp. 209–216] conjectured that every uniquely 3-colourable planar graph with at least four vertices has two adjacent triangles. However, in the same year, Melnikov and Steinberg [L.S. Mel'nikov and R. Steinberg,One counterexample for two conjectures on three coloring, Discrete Math. 20 (1977), pp. 203–206.] disproved the conjecture by constructing a counterexample. In this paper, we prove that if a uniquely 3-colourable planar graphGhas at most 4 triangles thenGhas two adjacent triangles. Furthermore, for any, we construct a uniquely 3-colourable planar graph withktriangles and without adjacent triangles. [ABSTRACT FROM PUBLISHER]

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]

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]

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]

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]

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]

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]

An acyclic coloring of a graph is a proper coloring of the graph, for which every cycle uses at least three colors. Let G 4 be the set of maximal planar graphs of minimum degree 4, such that each graph in G 4 contains exactly four odd-vertices and the subgraph induced by the four odd-vertices contains a quadrilateral. In this article, we show that every acyclic 4-coloring of a maximal planar graph with exact four odd-vertices is locally equitable with regard to its four odd-vertices. Moreover, we obtain a necessary and sufficient condition for a graph in G 4 to be acyclically 4-colorable, and give an enumeration of the acyclically 4-colorable graphs in G 4 . [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]