Search

A wide range of parameters of domination in graphs can be defined and studied through a common approach that was recently introduced in [] under the name of w-domination, where w = (w 0 , w 1 , ⋯ , w l) is a vector of non-negative integers such that w 0 ≥ 1 . Given a graph G, a function f : V (G) ⟶ { 0 , 1 , ⋯ , l } is said to be a w-dominating function if ∑ u ∈ N (v) f (u) ≥ w i for every vertex v with f (v) = i , where N(v) denotes the open neighbourhood of v ∈ V (G) . The weight of f is defined to be ω (f) = ∑ v ∈ V (G) f (v) , while the w-domination number of G, denoted by γ w (G) , is defined as the minimum weight among all w-dominating functions on G. A wide range of well-known domination parameters can be defined and studied through this approach. For instance, among others, the vector w = (1 , 0) corresponds to the case of standard domination, w = (2 , 1) corresponds to double domination, w = (2 , 0 , 0) corresponds to Italian domination, w = (2 , 0 , 1) corresponds to quasi-total Italian domination, w = (2 , 1 , 1) corresponds to total Italian domination, w = (2 , 2 , 2) corresponds to total { 2 } -domination, while w = (k , k - 1 , ⋯ , 1 , 0) corresponds to { k } -domination. In this paper, we show that several domination parameters of lexicographic product graphs G ∘ H are equal to γ w (G) for some vector w ∈ { 2 } × { 0 , 1 , 2 } l and l ∈ { 2 , 3 } . The decision on whether the equality holds for a specific vector w will depend on the value of some domination parameters of H. In particular, we focus on quasi-total Italian domination, total Italian domination, 2-domination, double domination, total { 2 } -domination, and double total domination of lexicographic product graphs. [ABSTRACT FROM AUTHOR]

In Chomp on graphs, two players alternatingly pick an edge or a vertex from a graph. The player that cannot move any more loses. The questions one wants to answer for a given graph are: Which player has a winning strategy? Can an explicit strategy be devised? We answer these questions (and determine the Nim-value) for the class of generalized Kneser graphs and for several families of Johnson graphs. We also generalize some of these results to the clique complexes of these graphs. Furthermore, we determine which player has a winning strategy for some classes of threshold graphs. [ABSTRACT FROM AUTHOR]