Abstract
Abstract. We show that if G is a cograph, that is P 4 -free, then for any graph H, γ(G H) ≥ γ(G)γ(H). By the characterization of cographs as a finite sequence of unions and joins of K 1 , this result easily follows from that of Bartsalkin and German. However, the techniques used are new and may be useful to prove other results.
Introduction
Vizing's conjecture [12] , now open for fifty-three years, states that for any two graphs G and H, γ(G H) ≥ γ(G)γ(H) (1.1) where γ(G) is the domination number of G.
The survey [4] discusses many results and approaches to the problem. For more recent partial results see [11] , [10] , [3] , [6] , [8] , and [9] .
A predominant approach to the conjecture has been to show it true for some large class of graphs. For example, in their seminal result, Bartsalkin and German [2] showed the conjecture for decomposable graphs. More recently, Aharoni and Szabó [1] showed the conjecture for chordal graphs and Brešar [3] gave a new proof of the conjecture for graphs G with domination number 3. We say that a bound is of Vizing-type if γ(G H) ≥ cγ(G)γ(H) for some constant c, which may depend on G or H. It is known [11] that all graphs satisfy the Vizing-type bound, γ(G H) ≥ 1 2 γ(G)γ(H) + 1 2 min{γ(G), γ(H)}.
Restricting the graphs, but as a generalization of Bartsalkin and German's class of decomposable graphs, Contractor and Krop [6] showed
where G belongs to A 1 , the class of graphs which are spanning subgraphs of domination critical graphs G ′ , so that G and G ′ have the same domination number and the clique partition number of G ′ is one more than its domination number.
Krop [8] showed that any claw-free graph G satisfies the Vizing-type bound
In this paper we show that the class of induced P 4 -free graphs, or cographs, satisfies Vizing's conjecture.
1.1. Notation. All graphs G(V, E) are finite, simple, connected, undirected graphs with vertex set V and edge set E. We may refer to the vertex set and edge set of G as V (G) and E(G), respectively. For more on basic graph theoretic notation and definitions we refer to Diestel [7] .
For any graph
The minimum cardinality of S ⊆ V , so that S dominates G is called the domination number of G and is denoted γ(G). We call a dominating set that realizes the domination number a γ-set.
The Cartesian product of two graphs
A graph G is a cograph or P 4 -free if it contains no induced P 4 subgraph. Let G be any graph and S a subset of its vertices. Chellali et al. [5] 
For any S ⊆ [k], say S = {i 1 , . . . , i s } where s ≥ 2. We may write P S as P {i 1 ,...,is} or P i 1 ,...,is interchangeably.
, we write Q I = i∈I Q i and call C (∪ i∈I Q i ) = i∈I Q i ∪ S⊆I P S the chamber of Q I . We may write this as
, where I h represents the indices of some cells in G-fiber G h , we write C I h to mean the chamber of
We may write {v i : i ∈ I h } for {v h i : i ∈ I h } when it is clear from context that we are talking about vertices of G H and not vertices of G.
For clarity, assume that our representation of G H is with G on the x-axis and H on the y-axis.
A cell which is not vertically dominated is vertically undominated.
In our argument, we label vertices of a minimum dominating set D of G H, by labels from [k] so that for any i ∈ [k], projecting the vertices labeled by i onto H produces a dominating set of H. We call a vertex (x, h) ∈ D h with the single label i, free, if there exists another vertex (y, h) ∈ D h , which is given the label i.
Cographs
Theorem 2.1. For any cograph G and any graph H, γ(G H) ≥ γ(G)γ(H).
Proof. Let Γ = {v 1 , . . . , v k } be a minimum [1, 2] dominating set of G and let D be a minimum dominating set of G H. By the result of Chellali et al. [5] (Theorem 8), γ(G) = k. Suppose u ∈ V (G) − {Γ} is adjacent to two vertices of Γ, say v 1 and v 2 . Notice that if neither v 1 nor v 2 have private neighbors with respect to Γ, then we could replace v 1 and v 2 by u in Γ and produce a smaller dominating set, which is a contradiction. Hence, at least one of P 1 or P 2 is nonempty.
Claim 2.2. There exists a vertex in P 1 ∪P 2 which is independent from both u and V (G) − {Q 1 ∪ Q 2 }.
Proof. Case 1: Suppose P 1 = ∅ and P 2 = ∅. Note that by the minimality of Γ no vertex of Γ − {v 2 } can be adjacent to v 2 . If w 1 ∈ P 1 , then by definition of private neighbors, no vertex of Γ − {v 1 } is adjacent to w 1 . If u is not adjacent to w 1 , then we produce P 4 : w 1 v 1 uv 2 which contradicts the definition of G. However, if u is adjacent to every vertex of P 1 , then we could replace v 1 and v 2 by u in Γ which would produce a smaller dominating set, which is impossible. Case 2: Suppose P 1 , P 2 = ∅. By minimality of Γ, some vertex of P 1 ∪ P 2 is not adjacent to u. Suppose such a vertex is w 2 ∈ P 2 . We may assume v 1 is adjacent to v 2 , else we would produce P 4 : w 2 v 2 uv 1 . For any vertex w 1 ∈ P 1 , we may assume w 1 is adjacent to w 2 , else we would produce P 4 : w 1 v 1 v 2 w 2 . Notice u is adjacent to w 1 to avoid P 4 :
} is adjacent to w 2 and suppose without loss of generality that u ′ is adjacent to v 3 .
Thus, we are left with the situation illustrated in Figure 2 where the drawn edges have been shown to exist. 
For any h ∈ V (H), suppose the fiber
may dominate any of v i 1 , . . . , v i ℓ . Thus, {v i : i ∈ I h } must be dominated horizontally in G h either by shared neighbors of {v i : i ∈ I h } or by vertices of {v i : 1 ≤ i ≤ k, i / ∈ I h }. Furthermore, the private neighbors {P h i : i ∈ I h } must be dominated horizontally in G h either by shared neighbors of {v i : i ∈ I h } or by vertices of {P
We label the vertices of D by the following Provisional Labeling. If a vertex of D h for any h ∈ H, is in Q h i for 1 ≤ i ≤ k, then we label that vertex by i. If v is a shared neighbor of some subset of {v i : i ∈ I h }, then it is a member of P h i,j for some i, j ∈ I h , and we label v by the pair of labels (i, j). If v is a member of
h , then we label v by either i or j arbitrarily. After the labels are placed, all vertices of D have a single label or a pair of labels.
Next, we apply a relabeling to some of the vertices of D which we call the First Refinement. For a fixed h ∈ H, suppose v is some shared neighbor of two vertices of {v i : i ∈ I h } in the chamber of Q h I h , which is vertically dominated, say by y ∈ D h ′ for some h ′ ∈ H, h = h ′ . In other words, we suppose v ∈ P h j 1 ,j 2 for some j 1 , j 2 ∈ I h which implies that y ∈ P h ′ j 1 ,j 2 . The vertex y may be labeled by one or two labels, regardless of whether the First Refinement had been performed on D h ′ .
Suppose that y is labeled by one label, say
, then we remove the pair of labels (j 1 , j 2 ) from x and relabel x by j 2 .
Suppose y is labeled by the pair of labels, (
, then we remove the pair of labels (j 1 , j 2 ) from x and then relabel x arbitrarily by one of the single labels j 1 or j 2 .
After the labeling, a vertex v of D may have a pair of labels (i, j) if v ∈ P h i,j
and for any h
Finally, we relabel some of the vertices of D by the Second Refinement. For every h ∈ H, if D h contains vertices x and y with pairs of labels (j 1 , j 2 ), (j 2 , j 3 ) respectively, for some integers j 1 , j 2 , and j 3 , then we relabel y by the label j 3 . If x and y are labeled j 1 and (j 1 , j 2 ) respectively, for some integers j 1 , j 2 , we relabel y by j 2 . We apply this relabeling to pairs of vertices of D h , sequentially, in any order. 
Proof. For any h ∈ V (H), suppose v ∈ D
h has a pair of labels (i, j). The Provisional Labeling prescribes that i, j ∈ I h which means that Q i and Q j are vertically undominated cells. If there exists w ∈ D h ∩ P j,m for any 1 ≤ m ≤ k, or x ∈ D h ∩ P j , then v would have a single label after the Second Refinement which is not the case. By Claim 2.2, some vertex x in P h i ∪ P h j is independent from v and independent from V (G) − {Q i ∪ Q j }. However, this means that x is undominated, which contradicts the fact that D is a dominating set.
Suppose that for some h ∈ V (H), G h contains a cell, Q 
To avoid a contradiction to the minimality of Γ, we see that P i = ∅ and say u ∈ P h i . Notice that if u is dominated by some u ′ ∈ P j 2 ∩ D h for some j 2 = i, j 1 , then we produce for any h ′ ∈ V (H). Finally, suppose u is dominated by some shared neighbor w ∈ P j 1 ,j 2 ∩D h . Notice if x ∈ P j 1 , then we produce P 4 : xv j 1 v i v j 2 and if y ∈ P j 2 , then we produce P 4 : yv j 2 v i v j 1 which cannot occur. Thus, P j 1 = P j 2 = ∅. If for every w ′ ∈ P j 1 ,j 2 , w is adjacent to w ′ , we have a contradiction to the minimality of Γ, since now we can replace v j 1 and v j 2 by the projection of w onto V (G) and form a smaller dominating set of G. We are left to suppose there exists w ′ ∈ P j 1 ,j 2 so that w ′ is not adjacent to w. To avoid P 4 : w ′ v j 1 wu, w ′ must be adjacent to u. Furthermore, this same property is true for any vertex v ∈ P j 1 ,j 2 not adjacent to w ′ or w, namely, v must be adjacent to u. To avoid P 4 : v j 2 w ′ v j 1 v i we must also have v j 2 adjacent to v i . At this point, notice that {v j 1 , v j 2 , P j 1 ,j 2 } is dominated by v i and u, which is a contradiction to the minimality of Γ, since now we can replace v j 1 and v j 2 in Γ by the projection of u onto V (G) and produce a smaller dominating set of G.
Notice that for any i ∈ [k], projecting all vertices with a label i to H produces a dominating set of H. Summing over all i, we count at least γ(G)γ(H) vertices in D.

{'paper_id': '119685421', 'title': "Vizing's conjecture for cographs", 's2_url': 'https://api.semanticscholar.org/CorpusID:119685421', 'source': 'S2ORC'}