Search

For a graph G = ( V , E ) , a double Roman dominating function is a function f : V ź { 0 , 1 , 2 , 3 } having the property that if f ( v ) = 0 , then vertex v must have at least two neighbors assigned 2 under f or one neighbor with f ( w ) = 3 , and if f ( v ) = 1 , then vertex v must have at least one neighbor with f ( w ) ź 2 . The weight of a double Roman dominating function f is the sum f ( V ) = ź v ź V f ( v ) , and the minimum weight of a double Roman dominating function on G is the double Roman domination number of G . We initiate the study of double Roman domination and show its relationship to both domination and Roman domination. Finally, we present an upper bound on the double Roman domination number of a connected graph G in terms of the order of G and characterize the graphs attaining this bound.

Let k ? 1 be an integer. A signed Roman k -dominating function on a graph G is a function f : V ( G ) ?s? { - 1 , 1 , 2 } such that ? u ? N v f ( u ) ? k for every v ? V ( G ) , where N v is the closed neighborhood of v , and every vertex u ? V ( G ) for which f ( u ) = - 1 is adjacent to at least one vertex w for which f ( w ) = 2 . A set { f 1 , f 2 , ? , f d } of distinct signed Roman k -dominating functions on G with the property that ? i = 1 d f i ( v ) ? k for each v ? V ( G ) , is called a signed Roman k -dominating family (of functions) on G . The maximum number of functions in a signed Roman k -dominating family on G is the signed Roman k -domatic number of G , denoted by d s R k ( G ) . In this paper we initiate the study of signed Roman k -domatic numbers in graphs, and we present sharp bounds for d s R k ( G ) . In particular, we derive some Nordhaus-Gaddum type inequalities. In addition, we determine the signed Roman k -domatic number of some graphs.

The classical first and second Zagreb indices of a graph G are defined as M 1 = ∑ v d v 2 and M 2 = ∑ u v d u d v , where d v is the degree of the vertex v of G . So far, the difference of M 1 and M 2 has not been studied. We show that this difference is closely related to the vertex-degree-based invariant R M 2 = ∑ u v ( d u − 1 ) ( d v − 1 ) , and determine a few basic properties of R M 2 .

Suppose that G is a graph and that H is a subgraph of G. Let L be a mapping that assigns to each vertex v of G a set L(v) of positive integers. We say that (G,H) is backboneL-colourable if there is a proper vertex colouring c of G such that c(v)@?L(v) for all [email protected]?V, and |c(u)-c(v)|>=2 for every edge uv in H. We say that (G,H) is backbone k-choosable if (G,H) is backbone L-colourable for any list assignment L with |L(v)|=k for all [email protected]?V(G). The backbone choice number of (G,H), denoted by ch"B"B(G,H), is the minimum k such that (G,H) is backbone k-choosable. The concept of a backbone choice number is a generalization of both the choice number and the L(2,1)-choice number. Precisely, if E(H)[email protected]?, then ch"B"B(G,H)=ch(G), where ch(G) is the choice number of G; if G=H^2, then ch"B"B(G,H) is the same as the L(2,1)-choice number of H. In this article, we first show that, if |L(v)|=d"G(v)+2d"H(v), then (G,H) is L-colourable, unless E(H)[email protected]? and each block of G is a complete graph or an odd cycle. This generalizes a result of Erdos, Rubin, and Taylor on degree-choosable graphs. Second, we prove that ch"B"B(G,H)=

Let f be a function that assigns to each vertex a subset of colors chosen from a set C={1,2,...,k} of k colors. If @?"u"@?"N"("v")f(u)=C for each vertex [email protected]?V with f(v)[email protected]?, then f is called a k-rainbow dominating function (kRDF) of G where N(v)={[email protected]?V|[email protected]?E}. The weight of f, denoted by w(f), is defined as w(f)[email protected]?"v"@?"V|f(v)|. Given a graph G, the minimum weight among all weights of kRDFs, denoted by @c"r"k(G), is called the k-rainbow domination number of G. [email protected]?ar and [email protected]?umenjak (2007) [5] gave an upper bound and a lower bound for @c"r"2(GP(n,k)). They showed that @[email protected]?=

Given a distribution of pebbles on the vertices of a connected graph G, a pebbling move on G consists of taking two pebbles off one vertex and placing one on an adjacent vertex. The t-pebbling [email protected]"t(G) is the smallest positive integer such that, for every distribution of @p"t(G) pebbles and every vertex v, t pebbles can be moved to v. For t=1, Graham conjectured that @p"1([email protected]?H)@[email protected]"1(G)@p"1(H) for any connected graphs G and H, where [email protected]?H denotes the Cartesian product of G and H. Herscovici further conjectured that @p"s"t([email protected]?H)@[email protected]"s(G)@p"t(H). In this paper, we show that @p"s"t([email protected]?G)@[email protected]"s(T)@p"t(G), @p"s"t(K"[email protected]?G)@[email protected]"s(K"n)@p"t(G) and @p"s"t(C"2"[email protected]?G)@[email protected]"s(C"2"n)@p"t(G) when G has the 2t-pebbling property, T is a tree, K"n is the complete graph on n vertices, and C"2"n is the cycle on 2n vertices, which confirms a conjecture due to Lourdusamy. Moreover, we also show that any graph G with diameter 2 and @p"t(G)[email protected](G)+4(t-1) has the 2t-pebbling property, which extends a result of Pachter et al.