For a graph \(G=(V(G), E(G))\), a subset \(S \subset V(G)\) is a bipartite dominating set if every vertex in \(G-S\) is adjacent to a vertex in \(S\), and if the subgraph of \(G\) induced by \(S\) is bipartite. The bipartite domination number of \(G\), denoted by \(\gamma_{bip}(G)\), is the minimum cardinality of all bipartite dominating sets of \(G\). Xi and Yue [4] claimed that for every 2-connected outerplanar \(n\)-vertex graph \(G\), \(\gamma_{bip}(G) \leq \lceil \frac n 3 \rceil\), and that this bound is sharp. In this paper, correcting the result, we prove that \(\gamma_{bip}(G) \leq \lceil \frac 38 n \rceil\), where this bound is sharp.
For a graph \(G=(V(G), E(G))\), a subset \(S \subset V(G)\) is a dominating set if every vertex in \(G-S\) is adjacent to a vertex in \(S\). The domination number of \(G\), denoted by \(\gamma(G)\), is the minimum cardinality of all dominating sets in \(G\). There is a significant amount of research on domination in graphs, as referenced in [3].
Bachstein et al. [1] gave a concept of “bipartite domination”, as follows. For a graph \(G\), a subset \(S \subset V(G)\) is a bipartite dominating set if \(S\) is a dominating set of \(G\) such that the subgraph of \(G\) induced by \(S\), denoted by \(G[S]\), is bipartite. We note that every graph \(G\) admits a bipartite dominating set, since we can take a maximal independent set in \(G\) as a bipartite dominating set. The bipartite domination number of \(G\), denoted by \(\gamma_{bip}(G)\), is the minimum cardinality of all bipartite dominating sets in \(G\). By definition, it is evident that \(\gamma_{bip}(G) \geq \gamma(G)\) for all graphs \(G\).
An outerplanar graph \(G\) is one with a planar embedding such that all vertices are incident to the boundary of the infinite face. Xi and Yue studied the bipartite domination on outerplanar graphs [4]. They first pointed out that an \(n\)-vertex outerplanar graph with cut vertices can have a large bipartite domination number close to \(n\). Then, restricting graphs to be 2-connected, they presented the following:
Theorem 1.1 (Xi and Yue [4]). Let \(G\) be a 2-connected \(n\)-vertex outerplanar graph. Then
\[ \gamma_{bip}(G) \leq \left\lceil \frac{n}{3} \right\rceil, \]where the estimation is sharp.
In this paper, correcting Theorem 1.1, we prove the following:
Theorem 1.2. Let \(G\) be a 2-connected \(n\)-vertex outerplanar graph. Then
\[ \gamma_{bip}(G) \leq \left\lceil \frac{3}{8}n \right\rceil, \]where the estimation is sharp for any positive integer \(n \equiv 0 \bmod 8\).
Let \({\cal G}_n\) be the set of all 2-connected \(n\)-vertex outerplanar graphs, where \(n \geq 3\). It is easy to see that \(\gamma(G) \leq \lceil \frac{n}{3} \rceil\) for any \(G \in {\cal G}_n\), Moreover, it was proved in [2] that \(i(G) \leq \frac{2n+1}{5}\) for any \(G \in {\cal G}_n\), where \(i(G)\) denotes the independent domination number of a graph \(G\), that is, the minimum cardinality of a dominating set \(S\) which is also an independent set in \(G\). Since the above two results are best possible and since \(\gamma(G) \leq \gamma_{bip}(G) \leq i(G)\) for all graphs \(G\), it follows that:
\[ \left\lceil \frac{n}{3} \right\rceil \leq \max_{G \in {\cal G}_n} \gamma_{bip}(G) \leq \frac{2n+1}{5}. \]Then Theorem 1.2 asserts that \(\max_{G \in {\cal G}_n} \gamma_{bip}(G) = \lceil \frac{3}{8}n \rceil\).
We first establish the sharpness of Theorem 1.2, as follows. A \(k\)-vertex means a vertex of degree \(k\), and a \(k\)-cycle a cycle of length \(k\).
Theorem 2.1. For \(m \geq 1\), there exists a 2-connected outerplanar graph \(G\) with \(8m\) vertices such that \(\gamma_{bip}(G) = 3m\).
Proof. Let \(H_i\) be the graph shown in Figure 1(1), for \(i=1,\ldots,m\), and let \(G_m\) be the outerplanar graph with \(8m\) vertices obtained from \(H_1,\ldots,H_m\) by connecting \(z_i\) and \(x_{i+1}\), as in Figure 1(2), where the subscripts are taken modulo \(m\). If we let \(S=\bigcup_{i=1}^m \{b_i, d_i,z_i\}\) as in Figure 1(3), then \(S\) is a bipartite dominating set with \(|S|=3m\).
Let \(T\) be any bipartite dominating set of \(G_m\). Let \(X_i=\{x_i, y_{i-1}, z_{i-1}\}\) and let \(A_i=\{a_i, b_i, c_i, d_i, e_i\}\), for \(i=1,\ldots,m\). Observe that each \(X_i\) has at least one vertex in \(T\). Moreover, each \(A_i\) has at least two vertices in \(T\) even if \(x_i, y_i \in T\), where we note that \(x_i,y_i,c_i\) cannot be contained in \(T\) simultaneously, since these three vertices induce a 3-cycle. Hence, \(|T| \geq 3m\) and consequently, \(\gamma_{bip}(G_m)=3m\). \(\square\)
Secondly, an upper bound of \(\gamma_{bip}(G)\) for a 2-connected outerplanar graph \(G\) is provided, and the proof follows the approach outlined in [4]. Recall that \({\cal G}_n\) denotes the set of all 2-connected \(n\)-vertex outerplanar graphs.
A configuration \(R\) in \(G \in {\cal G}_n\) is \(k\)-reducible if either of the following holds:
Xi and Yue used the following configurations for \(k=\frac{1}{3}\), and this argument holds for any \(k’ \geq \frac{1}{3}\). Hence we use those for \(k’ = \frac{3}{8}\).
Observe that \(G \in {\cal G}_n\) has a unique Hamilton cycle \(C\), and we always fix a planar drawing of \(G\) such that \(C\) is the boundary cycle of the infinite face. An edge \(xy \in E(G)\) is a chord of \(C\) if \(x,y \in V(G)\) but \(xy \notin E(C)\). A chord \(xy\) in \(G\) is short if \(x\) and \(y\) have distance at most 3 in \(C\), and long otherwise. A short chord \(xy\) has a triangle (resp., has a quadrilateral) if \(x\) and \(y\) have distance 2 (resp., 3) in \(C\).
The following are six \(\frac{1}{3}\)-reducible configurations established in [4] (see Figure 2).
Lemma 2.2 (Xi and Yue [4]). The configurations \({\cal Z}\), \({\cal TX}\), \({\cal TT}\), \({\cal TQ}\), \({\cal XXXX}\), \({\cal QX}\) are \(\frac{3}{8}\)-reducible.
In the following, we suppose that \(G \in {\cal G}_n\) has none of the six configurations in Lemma 2.2. A configuration \({\cal QQQ}\) consists of three consecutive quadrilaterals \(xabc, cdef, fghy\), shown in the left of Figure 3, where \(x \ne y\), and \(\deg(a)=\deg(b)=\deg(d)=\deg(e)=\deg(g)=\deg(h)=2\), and \(\deg(x) \geq 4\), \(\deg(c) = \deg(f) = 4\), \(\deg(y) \geq 4\) .
Lemma 2.3. The configuration \({\cal QQQ}\) is \(\frac{3}{8}\)-reducible.
Proof. Suppose that \(G \in {\cal G}_n\) contains \({\cal QQQ}\), and let \(G’\) be the graph obtained from \(G\) by removing the eight vertices \(a,b,c,d,e,f,g,h\) and adding an edge \(xy\), as shown in Figure 3. If this operation makes multiple edges between \(x\) and \(y\), we replace the multiple edges with a single edge \(xy\). Since \(\deg(x) \geq 4\) and \(\deg(y) \geq 4\) by the definition, we have \(G’ \in {\cal G}_{n-8}\).
Suppose that \(G’\) has a bipartite dominating set \(S’\) with \(|S’| \leq \lceil \frac{3}{8} (n-8) \rceil\). If \(x, y \notin S’\), then \(S = S’ \cup \{a,d,g\}\) is a dominating set of \(G\) with \(|S| \leq \lceil \frac{3}{8} n \rceil\). If \(x \in S’\) or \(y \in S’\), say the former by symmetry, then \(S=S’ \cup \{b,e,h\}\) is one with \(|S| \leq \lceil \frac{3}{8} n \rceil\), where we note that \(S\) dominates \(y\) in \(G\) even if \(S’\) does not dominate \(y\) in \(G’-xy\). Moreover, \(G[S]\) is bipartite in both cases. Therefore, \(\gamma_{bip}(G) \leq \lceil \frac{3}{8} n \rceil\). \(\square\)
Let \({\cal P}\) be the configuration consisting of two quadrilaterals \(xabc\) and \(cdey\) with a long chord \(xy\), as shown in Figure 4(1), such that \(\deg(a)=\deg(b)=\deg(d)=\deg(e)=2\), \(\deg(c)=4\), and \(\deg(x) \geq 4\) and \(\deg(y) \geq 4\), where \(x,y\) are the feet of \({\cal P}\).
Lemma 2.4. Suppose that \(G \in {\cal G}_n\) has \({\cal P}\) with feet \(x,y\). Let \(E \subset E(G) \setminus E(C)\) be the set of edges incident to \(x\) or \(y\) except \(cx,cy,xy\), and let \(G’ \in {\cal G}_n\) be the one obtained from \(G\) by removing \(E\). If \(G’\) has a bipartite dominating set with cardinality at most \(\lceil \frac{3}{8}n\rceil\), then so does \(G\).
Proof. We may suppose \(E \ne \emptyset\), for otherwise, the lemma trivially holds. By assumption, \(G’\) has a bipartite dominating set \(S’\) with \(S’ \leq \lceil \frac{3}{8}n \rceil\). If \(S’\) is also a bipartite dominating set of \(G\), then we are done. Hence, we may suppose that the addition of \(E\) to \(G’\) creates an odd cycle in \(G[S’]\) through \(x\) or \(y\). Let \(x’ \ne a\) and \(y’ \ne e\) be the neighbors of \(x\) and \(y\) in \(C\), respectively.
We first suppose that an odd cycle arisen in \(G[S’]\) passes through one of \(x\) and \(y\), say \(x\). In this case, \(x \in S’\) and there is an edge \(xp \in E\) with some \(p \in S’\) in \(G\). If we let \(T’=\{a,b,c,d,e\} \cap S’\), then \(|T’| \geq 2\) in \(G’\), since \(S’\) cannot contain \(c,x,y\) in \(G’\) simultaneously. Let \(S = S’ \setminus \{T’ \cup \{x\} \} \cup \{b, e\}\). Observe that \(x\) is dominated by \(p \in S\). If \(S\) dominates \(x’\) as well, then \(S\) is a bipartite dominating set of \(G\) with \(|S| < |S’|\). On the other hand, if \(S\) does not dominate \(x’\), then \(\tilde{S}=S \cup \{x’\}\) is a required bipartite dominating set with \(|\tilde{S}| \leq |S’|\).
Secondly suppose that odd cycles through \(x\) and those through \(y\) appear. After dealing with odd cycles in \(G\) through \(x\) as above, we deal with those through \(y\), and consider whether \(y’\) should be contained in \(S\) instead of \(y\). We omit a detailed disposition on \(y\). \(\square\)
Let \(\tilde{\cal P}\) be the configuration obtained from \({\cal P}\) by adding the conditions \(\deg(x)=\deg(y)=4\) and introducing one more vertex \(z\) adjacent to \(y\) in \(C\), as shown in Figure 4(2), where \(x’ \ne a\) and \(z’ \ne y\) are the neighbors of \(x\) and \(z\) in \(C\) respectively, and \(x’, x, y, z, z’\) are all distinct.
Lemma 2.5. A configuration \(\tilde{\cal P}\) is \(\frac{3}{8}\)-reducible.
Proof. Suppose that \(G \in {\cal G}_n\) contains \(\tilde{\cal P}\), but \(G\) has none of \({\cal Z}\), \({\cal TX}\), \({\cal TT}\), \({\cal TQ}\), \({\cal XXXX}\), \({\cal QX}\) and \({\cal QQQ}\). If \(x’z’ \in E(C)\) (as shown in Figure 5(1)), then \(G\) contains either \({\cal TX}\) or \({\cal XXXX}\), a contradiction. Hence, if we let \(G’\) be the graph obtained from \(G\) by removing \(a,b,c,d,e,x,y,z\) and adding an edge \(x’z’\) (as shown in Figure 4(2)), then we have \(G’ \in {\cal G}_{n-8}\) with \(n-8 \geq 3\).
Suppose that \(G’\) has a bipartite dominating set \(S’\) with \(|S’| \leq \lceil \frac{3}{8} (n-8) \rceil\). Depending on whether \(x’\) and \(z’\) are contained in \(S’\), we have the following cases (see Figure 6):
Then \(G'[S’]\) is bipartite, and thus \(S\) is a required dominating set of \(G\) with \(|S| \leq \lceil \frac{3}{8} n \rceil\). \(\square\)
Now we prove Theorem 1.2.
Proof of Theorem 1.2. Let \(G \in {\cal G}_n\) be a minimal couterexample of Theorem 1.2. Hence \(G\) has none of the \(\frac{3}{8}\)-reducible configurations \({\cal Z}\), \({\cal TX}\), \({\cal TT}\), \({\cal TQ}\), \({\cal XXXX}\), \({\cal QX}\), \({\cal QQQ}\), \(\tilde{{\cal P}}\). (For, if \(G\) contains one of them, then \(\gamma_{bip}(G) \leq \lceil \frac{3}{8}n\rceil\) or we can take a smaller 2-connected outerplanar graph \(G’\). Since \(G’\) satisfies the conclusion by the minimality, so does \(G\), by the property of a \(\frac{3}{8}\)-reducible configuration, a contradiction.) Let \(C\) be a unique Hamiltonian cycle of \(G\).
We first suppose that \(G\) has no long chord of \(C\). If \(G\) has no short chord either, then \(G\) is an \(n\)-cycle, which clearly satisfies \(\gamma_{bip}(G) \leq \lceil \frac{n}{3} \rceil \leq \lceil \frac{3}{8} n \rceil\). So \(G\) has short chords \(\ell\), but we observe that \(\ell\) has no triangle. (For, a short chord \(\ell=xb\) has a triangle \(xab\). Then either \(\deg(b)=3\) or \(\deg(b) \geq 4\). In the former case, \(G\) contains either \({\cal TX}\) or \({\cal Z}\), a contradiction. In the latter case, another short chord is incident to \(b\), and hence \(G\) contains either \({\cal TT}\), \({\cal TQ}\) or \({\cal Z}\), a contradiction.) Therefore, we may suppose that every short chord has a quadrilateral. Since \(G\) contains neither \({\cal QX}\) nor \({\cal QQQ}\), \(G\) must be isomorphic to the one in Figure 5(2), which has nine vertices with a bipartite dominating set with cardinality 3. This contradicts that \(G\) is a counterexample.
Secondly we suppose that \(G \in {\cal G}_n\) has a long chord \(xy\). Suppose that \(xy\) is chosen in \(G\) to be outermost, that is, at least one of \(L\) and \(L’\), say \(L\), has no long chord joining two vertices in \(L\), except \(xy\), where \(L\) and \(L’\) are the distinct paths in \(C\) joining \(x\) and \(y\) such that \(L \cup L’=C\). In this case, \(L\) is the \(C\)-path cut by \(xy\).
Now we show the following claim:
Claim. The subgraph of \(G\) induced by \(V(L)\) is isomorphic to \({\cal P}\) with feet \(x,y\).
Proof. Since \(xy\) is an outermost long chord of \(C\) in \(G\), the \(C\)-path \(L\) cut by \(xy\) has at least five vertices including \(x,y\). If \(L\) has no short chord, then \(L\) has at least three consecutive 2-vertices, contrary to \(G\) not having \({\cal XXXX}\). So \(L\) has short chords. Since all short chords have quadrilaterals but \(G\) contains neither \({\cal QX}\) nor \({\cal QQQ}\), \(L\) has exactly two short chords each of which has a quadrilateral. Therefore, \(G[V(L)]={\cal P}\). \(\square\)
We apply Lemma 2.4 to the configuration \({\cal P}\) with feet \(x,y\) which is found by the Claim. Then we may assume that \(\deg(x)=\deg(y)=4\) in \({\cal P}\), with the vertices of \({\cal P}\) as in Figure 4(1). Let \(x’ \ne a\) be the neighbor of \(x\) in \(C\). Let \(z \ne e\) be the neighbor of \(y\) in \(C\), and let \(z’ \ne y\) be the neighbor of \(z\) in \(C\), as in the left of Figure 4(2). Since \(xy\) is a long chord of \(C\), the vertices \(x’, x, y, z, z’\) are all distinct, and hence \(G\) has the configuration \(\tilde{\cal P}\). This contradicts the assumption on \(G\).
Therefore, every \(G \in {\cal G}_n\) satisfies that \(\gamma_{bip}(G) \leq \lceil \frac{3}{8}n \rceil\). \(\square\)
We would like to give a remark on what was wrong in Theorem 1.1 claimed in [4]. They established the six \(\frac{1}{3}\)-reducible configurations \({\cal Z}\), \({\cal TX}\), \({\cal TT}\), \({\cal TQ}\), \({\cal XXXX}\) and \({\cal QX}\), distinguishing short and long chords of a Hamiltonian cycle \(C\) of a 2-connected outerplanar graph \(G\), and fixed the graph \(D_m\) without those configurations, which is obtained from a \(3m\)-cycle \(a_1b_1c_1 a_2b_2c_2 \cdots a_m b_m c_m\) with short chords \(a_ia_{i+1}\) for each \(i\) and several long chords, where the subscripts are taken modulo \(m\). Then \(S=\{b_1,\ldots,b_m\}\) is a bipartite dominating set of \(D_m\) with \(|S|=\frac{|V(D_m)|}{3} = m\). Figure 7(1) shows \(D_{12}\) and its bipartite dominating set with \(m=12\) vertices.
However, a 2-connected outerplanar graph \(G\) might contain a quadrilateral \(xabc\) with a short chord \(xc\) and a long chord incident to \(c\) (shown in Figure 7(2)), since this configuration is not \({\cal QX}\) by the degree condition of \(c\). Then using these configurations, we can construct the 2-connected outerplanar graph \(G_m\) with \(m=8n\), shown in Figure 1(2), such that \(\gamma_{bip}(G) = \frac{3n}{8} > \frac{n}{3}\) for \(n \equiv 0 \bmod 8\). Consequently, we establish Theorem 1.2, giving a sharp bound \(\gamma_{bip}(G) \leq \lceil \frac{3}{8}n \rceil\) for a 2-connected \(n\)-vertex outerplanar graph \(G\).
