Graphs with equal domination and covering numbers

In this paper, we follow the notation of Chartrand et al. (2015). Let \(G=(V_G,E_G)\) be a graph with vertex set \(V_G\) and edge set \(E_G\). For a vertex v of G, its neighborhood, denoted by \(N_{G}(v)\), is the set of all vertices adjacent to v, and the cardinality of \(N_G(v)\), denoted by \(\deg _G(v)\), is called the degree of v. The minimum degree of a vertex in G is denoted by \(\delta (G)\). A leaf is a vertex of degree one, whereas a support vertex (or support, for short) is a vertex adjacent to a leaf. A weak support is a vertex adjacent to exactly one leaf. The set of leaves and supports of a graph G are denoted by \(L_G\) and \(S_G\), respectively. The closed neighborhood of v, denoted by \(N_{G}[v]\), is the set \(N_{G}(v)\cup \{v\}\). In general, the neighborhood of X, denoted by \(N_{G}(X)\), is defined to be \(\bigcup _{v\in X}N_{G}(v)\), and the closed neighborhood of X, denoted by \(N_{G}[X]\), is the set \(N_{G}(X)\cup X\). If X is a set of vertices of a graph G and \(x\in X\), then the private neighborhood of x with respect to X is the set \(PN_G[x,X]=N_G[x]- N_G[X-\{x\}]\), and each vertex in \(PN_G[x,X]\) is called a private neighbor of x with respect to X. Finally, the distance between two vertices u and v in G is denoted by \(d_G(u,v)\), and the diameter of G is \(\mathrm{diam}(G)=\max \{ d_G(u,v) :u,v \in G\}\).

A subset D of \(V_G\) is a dominating set of a graph G if each vertex belonging to the set \(V_G -D\) has a neighbor in D. The cardinality of a minimum dominating set of G is called the domination number of G and is denoted by \(\gamma (G)\). Every minimum dominating set of G is called a \(\gamma \)-set of G. A subset \(C \subseteq V_G\) is a covering set of G if each edge of G has an end-vertex in C. The cardinality of a minimum covering set of G is called the covering number of G and is denoted by \(\beta (G)\). Any minimum covering set of G is called a \(\beta \)-set of G. Finally, a subset \(I \subseteq V_G\) is said to be independent in G if no two vertices in it are adjacent. The cardinality of a maximum independent set of G is called the independence number of G and is denoted by \(\alpha (G)\). A maximum independent set in G is called an \(\alpha \)-set of G. The set of all connected graphs G for which \(\gamma (G)=\beta (G)\) is denoted by \({\mathcal {C}}_{\gamma =\beta }\), whereas \({\mathcal {B}}\) denotes the set of all connected bipartite graphs in which the domination number is equal to the cardinality of the smaller partite set. It is easy to observe that the complete graph \(K_n\) is in \({\mathcal {C}}_{\gamma =\beta }\) if and only if \(n=2\), the cycle \(C_n\) is in \({\mathcal {C}}_{\gamma =\beta }\) if and only if \(n=4\), the path \(P_n\) is in \({\mathcal {C}}_{\gamma =\beta }\) if and only if \(n\in \{2, 3, 4, 5, 7\}\), whereas the complete bipartite graph \(K_{m,n}\) is in \({\mathcal {C}}_{\gamma =\beta }\) if and only if \(\min \{m,n\}\in \{1, 2\}\).

The problem of characterizing the set \({\mathcal {C}}_{\gamma =\beta }\) was posed by Laskar and Walikar (1981). Volkmann (1994) have characterized some subsets of \({\mathcal {C}}_{\gamma =\beta }\). A first complete characterization of the set \({\mathcal {C}}_{\gamma =\beta }\) was given by Hartnell and Rall (1995), and independently by Randerath and Volkmann (1998). A simpler characterization was then provided by Wu and Yu (2012), and eventually Arumugam et al. (2013) proposed another yet characterization, also studying the problem for hypergraphs. Another subset of \({\mathcal {C}}_{\gamma =\beta }\), the set of all connected graphs G in which \(\gamma (H) = \beta (H)\) for every non-trivial connected induced subgraph H of G, was characterized in Arumugam et al. (2013) and Dettlaff et al. (2016).

In this paper, in Theorem 1, we provide an alternative characterization of the set \({{\mathcal {C}}}_{\gamma =\beta }\) in terms of \(\alpha \)-sets. Since \(\alpha \)-sets and \(\beta \)-sets are related by the Gallai’s theorem (Gallai 1959), our characterization is natural (with respect to relations between \(\gamma , \beta \), and \(\alpha \)), however, from the algorithmic point of view, our characterization is less practical than, for example, that in Arumugam et al. (2013), which allows to recognize whether a graph G belongs to \({\mathcal {C}}_{\gamma =\beta }\) in \(O(\sum _{v \in V_G} \deg ^2(v))\) time, whereas ours—does not. Next, in Theorem 2, we provide an alternative characterization of the graphs belonging to the set \({\mathcal {B}}\). Then, in Theorem 3, we provide a constructive characterization of all the trees in the set \({\mathcal {B}}\). Next, we discuss a quadratic time algorithm for recognizing bipartite graphs belonging to the set \({\mathcal {B}}\), and then, based upon an analogous argument, we conclude that the algorithm of Arumugam et al. (2013) recognizes all the graphs belonging to the set \({\mathcal {C}}_{\gamma =\beta }\) in quadratic time either. Finally, we consider the related problem of patrolling grids with mobile guards, and show that this problem can be solved in \(O(n \log n + m)\) time, where n is the number of line segments of the input grid and m is the number of its intersection points. We emphasize that our proof techniques are similar to those in Arumugam et al. (2013), Hartnell and Rall (1995), Randerath and Volkmann (1998), Wu and Yu (2012), and so all the aforementioned non-constructive characterizations possess similarities.

In our characterizations of the graphs belonging to the set \({\mathcal {C}}_{\gamma =\beta }\) or \({\mathcal {B}}\) we use the following Gallai’s theorem which relates the cardinality of the largest independent set and the cardinality of the smallest covering set in a graph.

We now present a characterization of the graphs belonging to the set \({\mathcal {C}}_{\gamma =\beta }\) and give a self-contained proof of this characterization.

From Theorem 1 we have the following two immediate corollaries.

Figure 1 shows a graph G belonging to the set \({\mathcal {C}}_{\gamma =\beta }\). In this case the solid vertices form an \(\alpha \)-set I of G, whereas \(V_G-I\) is a \(\gamma \)- and \(\beta \)-set of G. Certainly, I satisfies the conditions (1)–(3) of Theorem 1. On the other hand the graph F shown in Fig. 1 does not belong to the set \({\mathcal {C}}_{\gamma =\beta }\), as \(\gamma (F)=2\), whereas \(\beta (F)=3\). Thus, no \(\alpha \)-set I of F satisfies all three conditions (1)–(3) of Theorem 1. It is easy to check that the sets \(I_1 =\{v_2, v_4, v_6\}\), \(I_2 =\{v_1, v_4, v_6\}\), \(I_3 =\{v_1, v_3, v_5\}\) are the only \(\alpha \)-sets of F, and, in addition, the \(\alpha \)-set \(I_k\) (\(k\in \{1, 2, 3\}\)) satisfies precisely the conditions \(\{(1), (2), (3)\}-\{(k)\}\) of Theorem 1.

It is obvious that if \(G = ((A,B),E_G)\) is a bipartite graph, then each of the sets A and B is a dominating set in G and therefore \(\gamma (G) \le \min \{|A|,|B|\}\). For example, if A and B are partite sets of a path \(P_n\) (with \(n\ge 2\)) and \(|A|\le |B|\), then \(|A|= \lfloor n/2 \rfloor \), \(|B|=\lceil n/2 \rceil \), and \(\gamma (P_n)= \lceil n/3 \rceil \le \lfloor n/2 \rfloor =\min \{|A|,|B|\}\), in particular, \(\gamma (P_n) < \min \{|A|,|B|\}\) for \(n=6\) or \(n\ge 8\). Here we study graphs \(G = ((A,B),E_G)\) for which the equality \(\gamma (G) = \min \{|A|,|B|\}\) holds, that is, we study graphs belonging to the set \({\mathcal {B}}\) of bipartite graphs in which the domination number is equal to the cardinality of the smaller partite set. Such graphs were studied in Hartnell and Rall (1995) and Randerath and Volkmann (1998). Our characterization given in the next theorem is similar but different from those in Hartnell and Rall (1995) and Randerath and Volkmann (1998) [see Theorems 3.6 and 4.1 in Hartnell and Rall (1995), and Theorems 3.3 and 3.4 in Randerath and Volkmann (1998)]. Recently Miotk et al. (2019) observed that the graphs belonging to the set \({\mathcal {B}}\) can also be characterized in terms of some graph operations.

As an immediate consequence of Theorem 2 and its proof, we have the following results.

The corona\(F \circ K_1\) of a graph F is the graph formed from F by adding a new vertex \(v^{\prime }\) and edge \(vv^{\prime }\) for each vertex v of F. A graph G is said to be a corona graph if \(G = F \circ K_1\) for some graph F. We note that a graph G is a corona graph if and only if each vertex of G is a leaf or it is adjacent to exactly one leaf of G, and consequently every corona graph belongs to the set \({\mathcal {C}}_{\gamma =\beta }\). Payan and Xuong (1982) and Fink et al. (1985) have proved that for a connected graph G of even order is \(\gamma (G)=|V_G|/2\) if and only if G is the cycle \(C_4\) or the corona \(F\circ K_1\) for any connected graph F [see also Topp and Vestergaard (1995) for a short proof]. From this (or directly from Theorem 2) we immediately have the following corollary.

Simple examples illustrating relations between graphs considered in Theorems 1 and 2 , and Corollaries 1, 2, and 4–6 are shown in Fig. 2.

Let \({{\mathcal {T}}}_{{\max }}\) denote the set of trees for which the domination number is equal to the size of its smaller partite set. We now provide a constructive characterization of the trees belonging to the set \({{\mathcal {T}}}_{{\max }}\). Similar constructive characterizations of trees for different domination related parameters or properties have been presented in e.g. Alvarado et al. (2016), Henning and Klostermeyer (2017), Henning and Marcon (2016), and Rad (2017). Our characterization is based on four simple operations. To present these operations, we introduce some additional term. A vertex v of a graph G is called \(\gamma ^-\)-critical if \(\gamma (G-v) < \gamma (G)\) (or, equivalently, if \(\gamma (G-v) = \gamma (G)-1\)). Such vertices have been intensively studied [see e.g. Haynes and Henning (2003), Samodivkin (2008), and Sampathkumar and Neeralagi (1992)]. In particular, Sampathkumar and Neeralagi (1992) have observed that a vertex v of G is \(\gamma ^-\)-critical if and only if \(PN_G[v,D]=\{v\}\) for some \(\gamma \)-set D containing v.

Let \({{\mathcal {T}}}\) be the family of trees T that can be obtained from a sequence of trees \(T_0, \ldots , T_k\), where \(k\ge 0\), \(T_0=K_2\) and \(T=T_k\). In addition, if \(k\ge 1\), then for each \(i=1,\ldots ,k\), the tree \(T_i\) can be obtained from the tree \(T^{\prime }=T_{i-1}\) with the bipartition \((A^{\prime },B^{\prime })\), where \(|A^{\prime }| \le |B^{\prime }|\), by one of the following four operations \({{\mathcal {O}}}_1\), \({{\mathcal {O}}}_2\), \({{\mathcal {O}}}_3\), and \({{\mathcal {O}}}_4\) defined below and illustrated in Fig. 3.

Each of the vertices \(a^{\prime }\) in the above defined operations \({{\mathcal {O}}}_1\) and \({{\mathcal {O}}}_3\), and \(b^{\prime }\) in the operations \({{\mathcal {O}}}_2\) and \({{\mathcal {O}}}_4\), is called the attacher of \(T^{\prime }\). We shall prove that the trees in \({{\mathcal {T}}}\) are precisely the trees belonging to the family \({{\mathcal {T}}}_{{\max }}\). Our first aim is to show that each tree in \({{\mathcal {T}}}\) belongs to the family \({{\mathcal {T}}}_{{\max }}\). For this purpose we prove the following lemma.

We are now ready to provide a constructive characterization of the trees belonging to the family \({{\mathcal {T}}}_{{\max }}\).

Our characterization of graphs belonging to the set \({{\mathcal {C}}}_{\gamma =\beta }\), given in Theorem 1, is non-practical from algorithmic point of view, since this characterization involves \(\alpha \)-sets. However Theorem 2 allows us to propose a quadratic-time algorithm for recognizing bipartite graphs with the domination number equal to the size of the smaller partite set. The idea of our algorithm follows that in Arumugam et al. (2013) (see “Appendix” for the original algorithm), with the only difference of a slightly more thorough running time analysis, based upon the following obvious lemma.

The next corollary is immediate from Theorem 2 and Lemma 3.

Lemma 3 allows to conclude that all the graphs belonging to the set \({\mathcal {C}}_{\gamma =\beta }\) can also be recognized in \(O(n^2)\) time. Namely, Arumugam et al. (2013) proposed an algorithm that recognizes whether a given graph G belongs to the set \({\mathcal {C}}_{\gamma =\beta }\) in the claimed time complexity of \(O(\sum _{v \in V_G} \deg ^2(v))\) (again see “Appendix”). The most time consuming step in their algorithm (Step 3.2.4 in “Appendix”), after a preprocessing step for determining the relevant bipartition (A, B) of the subgraph H resulting from G by deleting all edges whose both end-vertices are support vertices, is to check whether for every non-support distinct vertices \(a,a^{\prime } \in A\), if a and \(a^{\prime }\) have some common neighbor, then they have at least two common neighbors of degree two, which takes \(O(\sum _{b \in B} \deg ^2_H(b))=O(\sum _{v \in V_G} \deg ^2(v))\) time in total. However, similarly as in the proof of Theorem 4, notice that a 2-element subset \(\{a,a^{\prime }\}\) of A can be checked at most \(n-2\) times, whereas at most n / 2 such subsets can ‘pass the test’ by Lemma 3 and Theorem 1.1 in Arumugam et al. (2013). Hence, we obtain the following corollary.

It is a natural question to ask whether the running time analysis of our algorithm [and that in Arumugam et al. (2013)] can be improved, say, to obtain the running time \(O(n^{2-\varepsilon })\) for some \(\varepsilon >0\). Showing that there exists an infinite class of bipartite graphs \(G=((A,B),E_G)\) in which the most time consuming step of our algorithm being of order \(\sum _{b \in B} |L(b)|^2\) can be \(\Theta (n^{2})\), we prove that this question has a negative answer. Let n and p be integers, where \(n\ge 16\) and \(p=\lfloor \sqrt{n}/2 \rfloor \). The multigraph of order p in which every two vertices are joined by exactly two multiple edges is denoted by \(K_p^{\prime \prime }\). Now let G be the graph obtained from the join \(K_p^{\prime \prime }+{\overline{K}}_{n-p^2}\) by subdividing each of its double edges exactly once (as illustrated in Fig. 4, where \(S(K_p^{\prime \prime })\) is the subdivision graph of \(K_p^{\prime \prime }\)). It is obvious that G is a leafless bipartite graph in which \(A=V_{K_p^{\prime \prime }}\) and \(B=V_G-A\) are partite sets and \(1<|A|=p<n-p= |B|\). Because sets \(L_G\) and \(S_G\) are empty, and for every distinct vertices x and y in A there are distinct vertices \({\overline{x}}\) and \({\overline{y}}\) in B such that \(N_G({\overline{x}})= N_G({\overline{y}})= \{x,y\}\), it follows from Theorem 2 that \(\gamma (G)=|A|\). On the other hand, it immediately follows from the construction of G that \(\sum _{v \in B} \deg ^2_G(v)= \Theta (n^2)\), and so our algorithm [and that in Arumugam et al. (2013)], when executed on G, will stop only after \(\Theta (n^2)\) steps. Of course, this example does not prove the quadratic lower bound for verifying the equality \(\gamma (G)=\beta (G)\) by any algorithm (cf. Arumugam et al. 2013, Remark 4.2, p. 1865).

We finalize our paper with a practical application of Theorem 4 in guarding grids. Namely, let \({{\mathcal {S}}}=\{S_1,S_2,\ldots ,S_n \}\) be a family of distinct vertical and horizontal closed line segments in the plane, where every two collinear line segments are disjoint. This family is called a grid if \(n\ge 2\) and the union \(\bigcup {{\mathcal {S}}}= S_1 \cup S_2 \cup \cdots \cup S_n\) is a connected subset of \({\mathbb {R}}^2\). The intersection graph of the family \({{\mathcal {S}}}\) is denoted by \(G_{{\mathcal {S}}}\) (and it is the graph with vertex-set \({{\mathcal {S}}}\) and edge-set \(\{S_iS_j:i\not =j, \,\,S_i, S_j\in {{\mathcal {S}}},\,\, \text{ and } \,\, S_i\cap S_j\not =\emptyset \}\)). It is obvious that if \({{\mathcal {S}}}\) is a grid, then \(G_{{\mathcal {S}}}\) is a connected bipartite graph and the pair \((V_{{\mathcal {S}}},H_{{\mathcal {S}}})\) is its bipartition, where \(V_{{\mathcal {S}}}\) (\(H_{{\mathcal {S}}}\), resp.) is the set of all vertical (horizontal, resp.) line segments of \({{\mathcal {S}}}\) (Ntafos 1986). An example of a grid \({\mathcal {S}}\) and the intersection graph \(G_{{\mathcal {S}}}\) (corresponding to the family \({{\mathcal {S}}}= V_{{\mathcal {S}}}\cup H_{{\mathcal {S}}}\), where \(V_{{\mathcal {S}}}=\{x, y,z, u,v\}\) and \(H_{{\mathcal {S}}}=\{a, b, c, d, e, f, g, h\}\)) are shown in Fig. 5.

A mobile guard is a guard traveling along a line segment of a grid, and patrolling this line segment and all the intersected line segments. We identify a mobile guard traveling along a line segment x with the same segment x and say that x patrols itself and the line segments intersected by x. A set \({\mathcal {C}}\subseteq {\mathcal {S}}\) of mobile guards is called a patrolling set of the grid \({\mathcal {S}}\) if every line segment \(x\in {{\mathcal {S}}}\) is either an element of \({{\mathcal {C}}}\) or is intersected by an element of \({{\mathcal {C}}}\). The problem of mobile guards patrolling a grid is a variant of the traditional art gallery problem and it was formulated by Ntafos (1986), and then its next variants were studied in a number of papers, see, for example, Bose et al. (2013), Brimkov (2013), Dumitrescu et al. (2014), Fekete et al. (2018), Katz et al. (2005), Korman et al. (2017) and Tan and Jiang (2018). Katz et al. (2005) observed that the decision problem associated with finding the minimum cardinality of a set of mobile guards patrolling a given grid is NP-complete. On the other hand it is obvious that all vertical line segments of a grid \({\mathcal {S}}\) (as well as all horizontal line segments of \({\mathcal {S}}\)) form a patrolling set of \({\mathcal {S}}\) and therefore the smallest number of mobile guards patrolling \({\mathcal {S}}\) is at most \(\min \{|V_{{\mathcal {S}}}|,|H_{{\mathcal {S}}}|\}\). A grid \({\mathcal {S}}\) is said to be extremal if the number of mobile guards required to patrol \({\mathcal {S}}\) is equal to \(\min \{|V_{{\mathcal {S}}}|,|H_{{\mathcal {S}}}|\}\), and we refer to the problem of recognizing extremal grids as the extremal guard cover problem. From the obvious fact that a subset \({\mathcal {C}}\) of a grid \({\mathcal {S}}\) is a set of mobile guards patrolling \({{\mathcal {S}}}\) if and only if \({\mathcal {C}}\) is a dominating set of the intersection graph \(G_{{\mathcal {S}}}\) (see Katz et al. 2005), it follows that \({\mathcal {S}}\) is an extremal grid if and only if \(G_{{\mathcal {S}}}\) is a bipartite graph in which the domination number is equal to the cardinality of the smaller of bipartite sets of the graph \(G_{{\mathcal {S}}}\). Thus the extremal guard cover problem for a grid \({\mathcal {S}}\) with n line segments can be solved by considering the intersection graph \(G_{{\mathcal {S}}}\) [which can be constructed in \(O(n \log n + m)\) time, where \(m=O(n^2)\) is the number of intersection points of line segments of \({\mathcal {S}}\), see Balaban (1995)] and then recognizing whether the domination number of \(G_{{\mathcal {S}}}\) is equal to \(\min \{|V_{{\mathcal {S}}}|,|H_{{\mathcal {S}}}|\}\), which can be done in \(O(n^2)\) time (by Theorem 4). However, since here geometry is involved and intersection graphs of grids form a restricted class of bipartite graphs, some significant improvement in the last statement is possible. We begin with the following lemma.

The next corollary is immediate from Lemma 4 and Theorem 2.

In our last theorem we present the announced time complexity upper bound for the extremal guard cover problem.