Search

A double Roman dominating function (DRDF) on a graph G = (V , E) is a function f : V → { 0 , 1 , 2 , 3 } satisfying (i) if f (v) = 0 then there must be at least two neighbors assigned two under f or one neighbor w with f (w) = 3 ; and (ii) if f (v) = 1 then v must be adjacent to a vertex w such that f (w) ≥ 2. A DRDF is an outer-independent total double Roman dominating function (OITDRDF) on G if the set of vertices labeled 0 induces an edgeless subgraph and the subgraph induced by the vertices with a non-zero label has no isolated vertices. The weight of an OITDRDF is the sum of its function values over all vertices, and the outer-independent total Roman domination number γ tdR oi (G) is the minimum weight of an OITDRDF on G. In this paper, we establish various bounds on γ tdR oi (G). In particular, we present Nordhaus–Gaddum-type inequalities for this parameter. Some of our results improve the previous results. [ABSTRACT FROM AUTHOR]

A restrained Italian dominating function (RIDF) on a graph G = (V , E) is a function f : V → { 0 , 1 , 2 } satisfying: (i) f (N (u)) ≥ 2 for every vertex u ∈ V (G) with f (u) = 0 , where N (u) is the set of vertices adjacent to u ; (ii) the subgraph induced by the vertices assigned 0 under f has no isolated vertices. The weight of an RIDF is the sum of its function values over the whole set of vertices, and the restrained Italian domination number γ r I (G) is the minimum weight of an RIDF on G. In this paper, we initiate the study of the restrained Italian bondage number b r I (G) of a graph G with no isolated vertices defined as the smallest size of set of edges F ⊆ E (G) for which γ r I (G − F) > γ r I (G). We begin by showing that the decision problem associated with the restrained Italian bondage problem is NP-hard. Then basic properties of the restrained Italian bondage number are presented. Finally, some sharp bounds for b r I (G) are also established. [ABSTRACT FROM AUTHOR]

The modified Sombor index of a graph G is defined as the sum of weights 1 / d u 2 + d v 2 over all edges u v of G , where d u and d v are the degrees of the vertices u and v in G , respectively. In this paper, we give a sharp lower bound on the modified Sombor index of unicyclic graphs with given diameter in terms the number of vertices. [ABSTRACT FROM AUTHOR]

Let k be a positive integer. A restrained k -rainbow dominating function (RkRD-function) of a graph G = (V , E) is a function f from the vertex set V to the set of all subsets of the set { 1 , 2 , ... , k } satisfying: (i) for any vertex v ∈ V with f (v) = ∅ the condition ⋃ u ∈ N (v) f (u) = { 1 , 2 , ... , k } is fulfilled, where N (v) is the set of all vertices adjacent to v ; (ii) the subgraph induced by the vertices assigned ∅ under f has no isolated vertices. The weight of an RkRD-function f is the value ω (f) = ∑ v ∈ V | f (v) | , and the restrained k -rainbow domination number of G , denoted by γ r r k (G) , is the minimum weight of an RkRD-function of G. In this paper, we continue the study of the restrained k -rainbow reinforcement number r r r k (G) of a graph G defined as the cardinality of a smallest set of edges that we must add to G to decrease γ r r k (G). We shall first show that the decision problem associated with γ r r k (G) is NP-hard for arbitrary graphs. Then several properties as well as some sharp bounds of the restrained k -rainbow reinforcement number are investigated. [ABSTRACT FROM AUTHOR]

Let G be a graph of order n and d i be the degree of the vertex v i , for i = 1 , 2 , ... , n. The ISI matrix of G is the square matrix of order n whose (i , j) -entry is equal to d i d j d i + d j if v i is adjacent to v j , and zero otherwise. Let μ 1 ≥ μ 2 ≥ ⋯ ≥ μ n , be the eigenvalues of ISI matrix. The ISI energy of a graph G , denoted by ξ ISI (G) , is defined as the sum of the absolute values of the eigenvalues of ISI matrix. In this paper, we prove that the star has the minimum ISI energy among trees. [ABSTRACT FROM AUTHOR]

The forgotten topological index (F -index) of a graph G , denoted by F (G) , is defined as the sum of cubes of the degrees of all the vertices in a graph. A connected graph with equal order and size is called unicyclic graph, where order is number of vertices and size is number of edges. In this paper, we investigate the new sharp upper bounds on F -index in terms of the order and maximum degree. [ABSTRACT FROM AUTHOR]

Let G be a graph with n vertices, and let d u be the degree of the vertex u in the graph G. The Randić matrix of G is the square matrix of order n whose (i , j) -entry is equal to (d u d v) − 1 2 if the vertex u and the vertex v of G are adjacent, and 0 otherwise. The Randić eigenvalues of G are the eigenvalues of its Randić matrix and the Randić energy of G is the sum of the absolute values of its Randić eigenvalues. In this paper, we obtain some new results for the Randić eigenvalues and the Randić energy of a graph. [ABSTRACT FROM AUTHOR]

Let k ≥ 1 be an integer, and let G be a graph. A k-rainbow dominating function (or k RDF) of G = (V , E) is a function f from the vertex set V (G) to the family of all subsets of { 1 , 2 , ... , k } such that for very v ∈ V (G) with f (v) = ∅ , the condition ⋃ u ∈ N G (v) f (u) = { 1 , 2 , ... , k } is fulfilled, where N G (v) is the open neighborhood of v. The weight of a k RDF f of G is the value ω (f) = ∑ v ∈ V (G) | f (v) |. A k-rainbow dominating function f in a graph with no isolated vertex is called a total k-rainbow dominating function if the subgraph of G induced by the set { v ∈ V (G) | f (v) ≠ ∅ } has no isolated vertices. The total k-rainbow domination number of G , denoted by γ t r k (G) , is the minimum weight of the total k -rainbow dominating function on G. The total k-rainbow reinforcement number of G , denoted by r t r k (G) , is the minimum number of edges that must be added to G in order to decrease the total k-rainbow domination number. In this paper, we investigate the properties of total k -rainbow reinforcement number in graphs. In particular, we present some sharp bounds for r t r k (G) and we determine the total k -rainbow reinforcement number of some classes of graphs including paths, cycles and complete bipartite graphs. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a graph and let f : V (G) → { 0 , 1 , 2 } be a function. A vertex v is 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, abbreviated CRDF if: (i) every vertex in V is protected, and (ii) each u ∈ V with positive weight has a neighbor v ∈ V with f (v) = 0 such that the function f u v : V → { 0 , 1 , 2 } , defined by f u v (v) = 1 , f u v (u) = f (u) − 1 and f u v (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 γ c r (G) , is the minimum weight of a co-Roman dominating function on G. In this paper, we present some new sharp bounds on γ c r (G). Some of our results improve the previous bounds. [ABSTRACT FROM AUTHOR]

A total Roman dominating function on a graph G is a labeling f : V (G) → { 0 , 1 , 2 } such that every vertex with label 0 has a neighbor with label 2 and the subgraph of G induced by the set of all vertices of positive weight has no isolated vertex. A set { f 1 , f 2 , ... , f d } of total Roman dominating functions on G with the property that ∑ i = 1 d f i (v) ≤ 2 for each v ∈ V (G) , is called a total Roman dominating family (of functions) on G. The maximum number of functions in a total Roman dominating family on G is the total Roman domatic number of G , denoted by d tR (G). In this paper, we investigate the properties of total Roman domatic number in graphs. In particular, we present some sharp bounds for d tR (G) and we determine the total Roman domatic number of some special graphs. [ABSTRACT FROM AUTHOR]

A signed total double Roman k -dominating function (STDRkDF) on an isolated-free graph G = (V , E) is a function f : V (G) → { − 1 , 1 , 2 , 3 } such that (i) every vertex v with f (v) = − 1 has at least two neighbors assigned 2 under f or at least one neighbor w with f (w) = 3 , (ii) every vertex v with f (v) = 1 has at least one neighbor w with f (w) ≥ 2 and (iii) ∑ u ∈ N (v) f (u) ≥ k holds for any vertex v. The weight of an STDRkDF is the value f (V (G)) = ∑ u ∈ V (G) f (u). The signed total double Roman k -domination number γ stdR k (G) is the minimum weight among all STDRkDFs on G. In this paper, we initiate the study of the signed total double Roman k -domination in graphs and present some sharp bounds for this parameter. In addition, we determine the signed total double Roman k -domination of paths for k ∈ { 2 , 3 }. [ABSTRACT FROM AUTHOR]

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 G = ( V , E ) be a simple graph with vertex set V and edge set E. A Roman dominating function on a graph G is a function f : V ( G ) → { 0 , 1 , 2 } satisfying the condition that every vertex u for which f ( u ) = 0 is adjacent to at least one vertex v for which f ( v ) = 2. A Roman dominating function f is called an independent Roman dominating function if the set of all vertices with positive weights is an independent set. The weight of an independent Roman dominating function f is the value f ( V ( G ) ) = ∑ u ∈ V ( G ) f ( u ). The independent Roman domination number of G , denoted by i R ( G ) , is the minimum weight of an independent Roman dominating function on G. A subset S of V is a 2-independent set of G if every vertex of S has at most one neighbor in S. The maximum cardinality of a 2-independent set of G is the 2-independence number β 2 ( G ). These two parameters are incomparable in general, however, we show that for any tree T , β 2 ( T ) ≥ i R ( T ) and we characterize all trees attaining the equality. [ABSTRACT FROM AUTHOR]

The harmonic index of a graph , denoted by , is defined as the sum of weights over all edges of , where denotes the degree of a vertex . Hu and Zhou [ WSEAS Trans. Math. 12 (2013) 716-726] proved that for any unicyclic graph of order , with equality if and only if . Recently, Zhong and Cui [ Filomat 29 (2015) 673-686] generalized the above bound and proved that for any unicyclic graph of order other than , . In this paper, we generalize the aforemention results and show that for any connected unicyclic graph of order with maximum degree , and classify the extremal unicyclic graphs. [ABSTRACT FROM AUTHOR]

A total Roman dominating function (TRDF) on a graph is a function satisfying the conditions (i) every vertex for which is adjacent at least one vertex for which and (ii) the subgraph of induced by the set of all vertices of positive weight has no isolated vertex. The weight of a TRDF is the sum of its function values over all vertices. A total Roman dominating function is called a global total Roman dominating function (GTRDF) if is also a TRDF of the complement of . The global total Roman domination number of is the minimum weight of a GTRDF on . In this paper, we initiate the study of global total Roman domination number and investigate its basic properties. In particular, we relate the global total Roman domination and the total Roman domination and the global Roman domination number. [ABSTRACT FROM AUTHOR]

Let be a finite and simple digraph. A -rainbow dominating function (RDF) of a digraph is a function from the vertex set to the set of all subsets of the set such that for any vertex with the condition is fulfilled, where is the set of in-neighbors of . The weight of a RDF is the value . The -rainbow domination number of a digraph , denoted by , is the minimum weight of a RDF of . The -rainbow reinforcement number of a digraph is the minimum number of arcs that must be added to in order to decrease the -rainbow domination number. In this paper, we initiate the study of -rainbow reinforcement number in digraphs and we present some sharp bounds for . In particular, we determine the -rainbow reinforcement number of some classes of digraphs. [ABSTRACT FROM AUTHOR]

Let be a commutative ring with identity. In this paper, we consider a simple graph associated with denoted by , whose vertex set is the set of all nonzero proper ideals of and two distinct vertices and are adjacent whenever or . In this paper, we initiate the study of the graph and we investigate its properties. In particular, we show that is a connected graph with unless is isomorphic to a direct product of two fields. Moreover, we characterize all commutative rings with at least two maximal ideals for which are planar. [ABSTRACT FROM AUTHOR]

A 2-rainbow dominating function (2RDF) of a graph is a function from the vertex set to the set of all subsets of the set such that for any vertex with , the condition is fulfilled. The weight of a 2RDF is the value . The -rainbow domination number of a graph , denoted by , is the minimum weight of a 2RDF of . The rainbow bondage number of a graph with maximum degree at least two is the minimum cardinality of all sets for which . Dehgardi, Sheikholeslami and Volkmann, [The -rainbow bondage number of a graph, Discrete Appl. Math. 174 (2014) 133-139] proved that the rainbow bondage number of a planar graph does not exceed 15. In this paper, we generalize their result for graphs which admit a -cell embedding on a surface with non-negative Euler characteristic. [ABSTRACT FROM AUTHOR]

A -rainbow dominating function (2RDF) of a graph is a function from the vertex set to the set of all subsets of the set such that for any vertex with the condition is fulfilled, where is the open neighborhood of . The weight of a 2RDF is the value . The -rainbow domination number of a graph , denoted by , is the minimum weight of a 2RDF of G. The -rainbow domination subdivision number is the minimum number of edges that must be subdivided (each edge in can be subdivided at most once) in order to increase the 2-rainbow domination number. It is conjectured that for any connected graph of order , . In this paper, we first prove this conjecture for some classes of graphs and then we prove that for any connected graph of order , . [ABSTRACT FROM AUTHOR]

A set S of vertices of a graph G = (V, E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination numberγt(G) is the minimum cardinality of a total dominating set of G. The game total domination subdivision number of a graph G is defined by the following game. Two players 풟 and 풜, 풟 playing first, alternately mark or subdivide an edge of G which is not yet marked nor subdivided. The game ends when all the edges of G are marked or subdivided and results in a new graph G′. The purpose of 풟 is to minimize the total domination number γt(G′) of G′ while 풜 tries to maximize it. If both 풜 and 풟 play according to their optimal strategies, γt(G′) is well defined. We call this number the game total domination subdivision number of G and denote it by γgt(G). In this paper we initiate the study of the game total domination subdivision number of a graph and present some (sharp) bounds for this parameter. [ABSTRACT FROM AUTHOR]

Let D be a simple digraph with arc set A(D), and let j and k be two positive integers. A function f : A(D) → {-1, 1} is said to be a signed star j-dominating function (SSjDF) on D if ∑a ∈ A(v) f(a) ≥ j for every vertex v of D, where A(v) is the set of arcs with head v. A set {f1, f2, ..., fd} of distinct SSjDFs on D with the property that for each a ∈ A(D), is called a signed star (j, k)-dominating (SS(j, k)D) family (of functions) on D. The maximum number of functions in a SS(j, k)D family on D is the signed star (j, k)-domatic number of D, denoted by . In this paper, we study properties of the signed star (j, k)-domatic number of a digraph D. In particular, we determine bounds on . Some of our results extend these ones given by Sheikholeslami and Volkmann [Signed star k-domination and k-domatic number of digraphs, submitted] for the signed (j, 1)-domatic number. [ABSTRACT FROM AUTHOR]

A set S of vertices of a graph G is a total outer-connected dominating set if every vertex in V(G) is adjacent to some vertex in S and the subgraph G[V\S] induced by V\S is connected. The total outer-connected domination number γtoc(G) is the minimum size of such a set. The total outer-connected domination subdivision number sdγtoc(G) is the minimum number of edges that must be subdivided in order to increase the total outer-connected domination number. We prove the existence of sdγtoc(G) for every connected graph G of order at least 3 and give upper bounds on it in some classes of graphs. [ABSTRACT FROM AUTHOR]