A dominating set in a graph G is a set S of vertices such that every vertex in V (G) \ S is adjacent to at least one vertex in S, and the domination number of G is the minimum cardinality of a dominating set of G. Placing constraints on a dominating set yields different domination parameters, including total, connected, restrained, and clique domination numbers. In this paper, we study relationships among domination parameters of a graph and its complement.

See supplemental content for abstract

In this paper, we continue the study of the domination game in graphs introduced by Brešar, Klavžar, and Rall [SIAM J. Discrete Math. 24 (2010) 979-991]. We study the paired-domination version of the domination game which adds a matching dimension to the game. This game is played on a graph G by two players, named Dominator and Pairer. They alternately take turns choosing vertices of G such that each vertex chosen by Dominator dominates at least one vertex not dominated by the vertices previously chosen, while each vertex chosen by Pairer is a vertex not previously chosen that is a neighbor of the vertex played by Dominator on his previous move. This process eventually produces a paired-dominating set of vertices of G; that is, a dominating set in G that induces a subgraph that contains a perfect matching. Dominator wishes to minimize the number of vertices chosen, while Pairer wishes to maximize it. The game paired-domination number γgpr(G) of G is the number of vertices chosen when Dominator starts the game and both players play optimally. Let G be a graph on n vertices with minimum degree at least 2. We show that γgpr(G) ≤ 45 n, and this bound is tight. Further we show that if G is (C4, C5)-free, then γgpr(G) ≤ 43 n, where a graph is (C4, C5)-free if it has no induced 4-cycle or 5-cycle. If G is 2-connected and bipartite or if G is 2-connected and the sum of every two adjacent vertices in G is at least 5, then we show that γgpr(G) ≤ 34 n.

A set S = {u1, u2,..., ut} of vertices of G is an efficient dominating set if every vertex of G is dominated exactly once by the vertices of S. Letting Ui denote the set of vertices dominated by ui, we note that {U1, U2,... Ut} is a partition of the vertex set of G and that each Ui contains the vertex ui and all the vertices at distance 1 from it in G. In this paper, we generalize the concept of efficient domination by considering k-efficient domination partitions of the vertex set of G, where each element of the partition is a set consisting of a vertex ui and all the vertices at distance di from it, where di ∈ {0, 1,..., k}. For any integer k ≥ 0, the k-efficient domination number of G equals the minimum order of a k-efficient partition of G. We determine bounds on the k-efficient domination number for general graphs, and for k ∈ {1, 2}, we give exact values for some graph families. Complexity results are also obtained.

The six classes of graphs resulting from the changing or unchanging of the domination number of a graph when a vertex is deleted, or an edge is deleted or added are considered. Each of these classes has been studied individually in the literature. We consider relationships among the classes, which are illustrated in a Venn diagram. We show that no subset of the Venn diagram is empty for arbitrary graphs, and prove that some of the subsets are empty for connected graphs. Our main result is a characterization of trees in each subset of the Venn diagram.

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∈Vf(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.

A perfect Italian dominating function on a graph G is a function f:V(G)→{0,1,2} satisfying the condition that for every vertex u with f(u)=0, the total weight of f assigned to the neighbors of u is exactly two. The weight of a perfect Italian dominating function is the sum of the weights of the vertices. The perfect Italian domination number of G, denoted γ Ip (G), is the minimum weight of a perfect Italian dominating function of G. We show that if G is a tree on n≥3 vertices, then γ Ip (G)≤[Formula presented]n, and for each positive integer n≡0(mod5) there exists a tree of order n for which equality holds in the bound.

Let G be a graph with vertex set V and no isolated vertices, and let S be a dominating set of V. The set S is a semitotal dominating set of G if every vertex in S is within distance 2 of another vertex of S. And, S is a semipaired dominating set of G if S can be partitioned into 2-element subsets such that the vertices in each 2-set are at most distance two apart. The semitotal domination number γt 2(G) is the minimum cardinality of a semitotal dominating set of G, and the semipaired domination number γpr 2(G) is the minimum cardinality of a semipaired dominating set of G. For a graph without isolated vertices, the domination number γ(G) , the total domination γt(G) , and the paired domination number γpr(G) are related to the semitotal and semipaired domination numbers by the following inequalities: γ(G) ≤ γt 2(G) ≤ γt(G) ≤ γpr(G) and γ(G) ≤ γt 2(G) ≤ γpr 2(G) ≤ γpr(G) ≤ 2 γ(G). Given two graph parameters μ and ψ related by a simple inequality μ(G) ≤ ψ(G) for every graph G having no isolated vertices, a graph is (μ, ψ) -perfect if every induced subgraph H with no isolated vertices satisfies μ(H) = ψ(H). Alvarado et al. (Discrete Math 338:1424–1431, 2015) consider classes of (μ, ψ) -perfect graphs, where μ and ψ are domination parameters including γ, γt and γpr. We study classes of perfect graphs for the possible combinations of parameters in the inequalities when γt 2 and γpr 2 are included in the mix. Our results are characterizations of several such classes in terms of their minimal forbidden induced subgraphs.

In honor of Professor Peter Slater's work on paired domination, we introduce a relaxed version of paired domination, namely semipaired domination. Let G be a graph with vertex set V and no isolated vertices. A subset S ⊆ V is a semipaired dominating set of G if every vertex in V \ S is adjacent to a vertex in S and S can be partitioned into two element subsets such that the vertices in each subset are at most distance two apart. The semipaired domination number γPr2(G) is the minimum cardinality of a semipaired dominating set of G. In this paper, we study the semipaired domination versus other domination parameters. For example, we show that γ(G) ≤ γPr2(G) ≤ 2γ(G) and 2/3γt(G) ≤ γPr2(T) ≤ γ 4/3γt(G), where γ(G) and γt(G) denote the domination and total domination numbers of G. We characterize the trees G for which γPr2(G) = 2γ(G).

We determine upper bounds on the ratios of several domination parameters in trees.