Distance domination, guarding and vertex cover for maximal outerplanar graphs

XV Spanish Meeting on Computational Geometry, June 26-28, 2013 Distance domination, guarding and vertex cover for maximal outerplanar graphs Santiago Canales 1 , Gregorio Hernández ∗ 2 , Mafalda Martins ‡† 3 , and Inês Matos ‡ 3 1 Universidad Ponticia Comillas de Madrid, Spain 2 Universidad Politécnica de Madrid, Spain 3 Universidade Aveiro & CIDMA, Portugal Abstract In this paper we dene a distance guarding concept on plane graphs and associate this concept with distance domination and distance vertex cover concepts on triangulation graphs. Furthermore, for any n -vertex maximal outerplanar graph, we provide tight upper bounds for g2d(n) ( 2d -guarding number), γ2d(n) ( 2d -domination number) and β2d(n) ( 2d -vertex cover number). Introduction Domination, covering and guarding are widely studied subjects in graph theory. Given a graph G= (V, E) a dominating set is a subset D of V such that every vertex not in D is adjacent to a vertex in D . A subset C of V is a vertex cover if each edge of the graph is incident to at least one vertex of the set. Thus, a dominating set guards the vertices of a graph while a vertex cover guards its edges . In plane graphs these concepts dier from the guarding set concept that guards the faces of the graph. Let G= (V, E) be a plane graph, a guarding set is a subset S of V such that every face has a vertex in S . There are many papers and books about domination and its many variants in graphs, e.g. [4, 8, 9, 10]. Domination was extended to distance domination by Meir and Moon [11]: given a graph G , a subset D of V is said to be a distance k -dominating set if for each vertex u∈V−D , distG(u, v)≤k for some v∈D . The minimum cardinality of a distance k -dominating set is said to be the distance k -domination number of G and is denoted by γkd(G) . In the case of distance domination, ∗ Research supported by ESF EUROCORES programme EuroGIGA - ComPoSe IP04 - MICINN Project EUI-EURC-2011- 4306. † Email: [email protected]. Research also supported by FCT grant SFRH/BPD/66431/2009. ‡ Research supported by FEDER funds through COMPETE Operational Programme Factors of Competitiveness, CIDMA and FCT within project PEst- C/MAT/UI4106/2011 with COMPETE number FCOMP- 01-0124-FEDER-022690. there are also some known results concerning bounds for γkd(G) , e.g., [13, 14]. However, if graphs are restricted to triangulations, as far as we know, there are no known bounds for γkd(G) . The distance domination was generalized to broadcast domination when the power of each vertex may vary [6]. Given a graph G= (V, E) , a broadcast is a function f:V→N0 . A broadcast is dominating if for every vertex v , there is a vertex u such that f(u)>0 and d(u, v)≤f(u) . A dominating broadcast f is optimal if ∑v∈Vf(v) is minimum over all choices of broadcast dominating functions for G . The broadcast domination problem consists in building this optimal function. Note that, if f(V) = {0, k} , then the broadcast domination problem is the distance k -dominating problem. If a broadcast f provides coverage to the edges of G instead of covering its vertices, we have a generalization of the vertex cover concept [2]. A broadcast f is covering if for every edge (x, y)∈E , there is a path P in G that includes the edge (x, y) and one end of P must be a vertex u , where f(u) is at least the length of P . A covering broadcast f is optimal if ∑v∈Vf(v) is minimum over all choices of broadcast covering functions for G . Note that, if f(V) = {0,1} , then the broadcast cover problem coincides with the problem of nding a minimum vertex cover. Regarding the broadcast cover problem when all vertices have the same power (i.e., when f(V) = {0, k} , for a xed k= 1 ), as far as we know, there are no published results besides [5] where the authors propose a centralized and distributed approximation algorithm to solve it. Concerning the guarding concept there are also known bounds on the guarding number g(G) . For example, g(G)≤ ⌊n 2⌋ , for any n -vertex plane graph [3], and if G is a maximal outerplanar graph this bound is ⌊n 3⌋ [7]. Contrary to the notions of domination and vertex cover on plane graphs that were extended to include its distance versions, the guarding concept was not generalized to its distance version. In this paper we generalize the guarding concept on plane graphs to its distance guarding version. We also formalize the broadcast cover problem when all vertices have the same power, which we call distance 51 Distance domination, guarding and vertex cover for maximal outerplanar graphs k -vertex cover . Since there are no combinatorial results for the concepts of domination, vertex cover and guarding on its distance versions on triangulation graphs ( triangulations , for short), we also address this problem. In the next section we describe some of the terminology that will be used throughout this paper. 1 Preliminaries Given a triangulation of a point set T= (V, E) , we say that a bounded face Ti of T (i.e., a triangle) is kd - visible from a vertex p∈V , if there is a vertex x∈Ti such that distT(x, p)≤k−1 . The kd -visibility region of a vertex p∈V comprises the triangles of T that are kd -visible from p (see Fig. 1). p p ( )a(b) Figure 1: The kd -visible region of p for: (a) k= 1 ; (b) k= 2 . A kd -guarding set for T is a subset F⊆V such that every triangle of T is kd -visible from an element of F . We designate the elements of F by kd -guards . The kd - guarding number gkd(T) is the number of vertices in a smallest kd -guarding set for T . Note that, to avoid confusion with multiple guarding [1] - where the typical notation is k -guarding - we will use kd -guarding, with an extra  d . Given a set S and a positive integer n , we dene gkd(S) = max{gkd(T) : T= (V, E) is triangulation with V=S} and gkd(n) = max{gkd(S) : |S|=n} . A kd -vertex cover for T , or distance k -vertex cover for T , is a subset C⊆V such that for each edge e∈E there is a path of length at most k , which contains e and a vertex of C . The kd -vertex cover number βkd(T) is the number of vertices in a smallest kd -vertex cover set for T . Given a set S and a positive integer n , we dene βkd(S) = max{βkd(S) : T= (V, E) is triangulation with V= S} and βkd(n) = max{βkd(S) : |S|=n} . Finally, as already dened by other authors, a kd -dominating set for T , or distance k -dominating set for T , is a subset D⊆V such that each vertex u∈V−D , distT(u, v)≤k for some v∈D . The kd -domination number γkd(T) is the number of vertices in a smallest kd -dominating set for T . Given a set S and a positive integer n , we dene γkd(S) = max{γkd(T) : T= (V, E) is triangulation with V=S} and γkd(n) = max{γkd(S) : |S|=n} . Our main goal is to obtain bounds on γkd(T) , gkd(T) and βkd(T) . We start by establishing a tight upper bound for g2d(n) for a special class of triangulations, namely the maximal outerplanar graphs . A graph is a maximal outerplanar graph if it is a triangulation of a simple polygon without holes [12]. Edges on the exterior face are called exterior edges , and interior edges otherwise. In the next section we show that there is a relationship between 2d -guarding, 2d -dominating and 2d -vertex cover sets on triangulations. In sections 3 and 4 we provide upper bounds for g2d(n) , γ2d(n) and β2d(n) on maximal outerplanar graphs and show that these bounds are tight. 2 Relationship between distance vertex cover, guarding and domination on triangulations We start by showing that the three concepts are different. Fig. 2 depicts 2d -dominating and 2d -guarding sets for a given triangulation. Note that in Fig. 2(a) the set {u, v} is 2d -dominating since the remaining vertices are at distance 1 or 2. However, it is not a 2d -guarding set because the shaded triangle is not guarded, as its vertices are at distance 2 from {u, v} . In 2(b) {w, z} is a 2d -guarding set, however it is not a 2d -vertex cover since any path between the bold edge and w or z has length at least 3. Therefore, the bold edge is not covered. uv w z ( )a(b) Figure 2: (a) 2d -dominating set for a triangulation T ; (b) 2d -guarding set for T . Now we are going to establish a relation between g2d(T) , γ2d(T) and β2d(T) . The following results can be easily generalized to gkd(T) , γkd(T) and βkd(T) . Lemma 1 If C is a 2d -vertex cover of a triangulation T , then C is a 2d -guarding set and a 2d -dominating set of T . Lemma 2 If F is a 2d -guarding set of a triangulation T , then F is a 2d -dominating set of T . The previous lemmas prove the following result. Theorem 3 Given a triangulation T the minimum cardinality g2d(T) of any 2d -guarding set veries γ2d(T)≤g2d(T)≤β2d(T) . 52 XV Spanish Meeting on Computational Geometry, June 26-28, 2013 (a) (b) (c) Figure 3: (a) A 2d -dominating set for a triangulation T (black vertices); (b) a 2d -guarding set for T (gray vertices); (c) each of the bold edges needs a dierent vertex to be 2d -covered. Note that the inequalities above can be strict, as we can see in the triangulation T presented in Fig. 3, where γ2d(T) = 2 , g2d(T) = 3 , and β2d(T)≥4 . 3 2d -domination and 2d - guarding of maximal outerplanar graphs In this section we establish upper bounds for g2d(n) and γ2d(n) on maximal outerplanar graphs. In order to do this, and following the ideas of O'Rourke [12], we rst need to introduce some lemmas. Lemma 4 Suppose that f(m) guards are always suf- cient to 2d -guard any outerplanar maximal graph G with m vertices. Then if G has two guards placed at any two adjacent vertices or one guard placed at any one of its vertices, then f(m−2) or f(m−1) additional guards are sucient to 2d -guard G , respectively. Lemma 5 Let G be an outerplanar maximal graph with n≥2k vertices. There is an interior edge e of G that partitions G into two pieces, one of which contains m=k, k + 1, . . . , 2k−1 or 2k−2 exterior edges of G . Theorem 6 Every n -vertex maximal outerplanar graph, with n≥5 , can be 2d -guarded by ⌊n 5⌋2d - guards. That is, g2d(n)≤ ⌊n 5⌋ for all n≥5 . Proof. For 5≤n≤11 , the truth of the theorem can be easily established. It should be noted that for n= 5 the 2d -guard can be placed randomly and for n= 6 it can be placed at any vertex of degree greater than 2. Assume that n≥12 and that the theorem holds for all n′< n . Lemma 5 guarantees the existence of an interior edge e that divides G into two maximal outerplanar graphs G1 and G2 , such that G1 has m exterior edges of G with 6≤m≤10 . The vertices of G are labeled with 0,1, . . . , n −1 such that e is (0, m) . Each value of m is considered separately. We present the cases m= 6 and m= 9 . Case m= 6 . G1 has m+ 1 = 7 exterior edges, thus G1 can be 2d -guarded with one guard. G2 has n−5 exterior edges including e , and by induction hypothesis, it can be 2d -guarded with ⌊n−5 5⌋=⌊n 5⌋−1 guards. Thus G1 and G2 together can be 2d -guarded by ⌊n 5⌋ guards. Case m= 9 . The presence of any of the internal edges (0,8), (0,7), (0,6), (9,1), (9,2) and (9,3) would violate the minimality of m . Thus, the triangle T in G1 that is bounded by e is either (0,5,9) or (0,9,4). Since these are equivalent cases, suppose that T is (0,5,9) (see Fig. 4(a)). 09 7 6 5 4 3 2 18 e G2 T G1 09 7 6 5 4 8 e G2 3 2 1T G1 ( )a( )b Figure 4: (a) The triangle T is (0,5,9); (b) the internal edge (0,4) and the triangle (6,7,8) are present. The pentagon (5,6,7,8,9) can be 2d -guarded by placing one guard at a chosen vertex. However, to 2d - guard the hexagon (0,1,2,3,4,5) we cannot place a guard randomly.We will consider two separate cases: ( i ) The internal edge (0,4) is not present: if a guard is placed at vertex 5, then the hexagon (0,1,2,3,4,5) is 2d -guarded, thus G1 is 2d -guarded. Since G2 has n−8 edges it can be 2d -guarded by ⌊n−8 5⌋ ≤ ⌊n 5⌋−1 guards applying the induction hypothesis. This yields a 2d -guarding of G by ⌊n 5⌋ guards; ( ii ) The internal edge (0,4) is present: if a guard is placed at vertex 0, then G1 is 2d -guarded unless the triangle (6,7,8) is present in the triangulation (see Fig. 4(b)). In any case, two 2d -guards placed at vertices 0 and 9 guard G1 . G2 has n−8 exterior edges, including e . By lemma 4 the two guards placed at vertices 0 and 9 allow the remainder of G2 to be guarded by f(n−8−2) = f(n−10) additional 2d -guards. Recall that f(n′) is the number of 2d -guards that are always sucient to guard a maximal outerplanar graph with 53 Distance domination, guarding and vertex cover for maximal outerplanar graphs n′ vertices. By the induction hypothesis f(n′) = ⌊n′ 5⌋ . Thus, ⌊n−10 5⌋=⌊n 5⌋−2 guards suces to 2d -guard G2 . Together with the guards placed at vertices 0 and 9 that 2d -guard G1 , all G is guarded by ⌊n 5⌋2d - guards.  To prove that this upper bound is tight we need to construct a maximal outerplanar graph G of order n such that g2d(G) = ⌊n 5⌋ . Fig. 5 shows a maximal outerplanar graph G for which γ2d(G) = n 5 , since the black vertices can only be 2d -dominated by different vertices. Thus, γ2d(n)≥n 5 . Note that this example can be generalized to kd -domination to obtain γkd(n)≥n (2k+1) . Figure 5: A maximal outerplanar graph G for which γ2d(G) = n 5 . According to theorem 3, γ2d(G)≤g2d(G) , so ⌊n 5⌋ ≤ g2d(G) . In conclusion, ⌊n 5⌋2d -guards are occasionally necessary and always sucient to guard a n -vertex maximal outerplanar graph G . On the other hand, we can also establish that γ2d=⌊n 5⌋ , since ⌊n 5⌋ ≤ γ2d(n) and γ2d(n)≤g2d(n) , for all n . Thus, it follows: Theorem 7 Every n -vertex maximal outerplanar graph with n≥5 can be 2d -guarded (and 2d - dominated) by ⌊n 5⌋ guards. This bound is tight. 4 2d -covering of maximal outerplanar graphs In this section we determine an upper bound for 2d - vertex cover on maximal outerplanar graphs which is also tight. Lemma 8 Suppose that f(m) vertices are always suf- cient to 2d -cover any outerplanar maximal graph G with m vertices. If we randomly choose a vertex of G to be a 2d -covering vertex, then f(m−1) additional vertices are sucient 2d -cover G . Theorem 9 Every n -vertex maximal outerplanar graph, with n≥4 , can be 2d -covered with ⌊n 4⌋ vertices. That is, β2d(n)≤ ⌊n 4⌋ for all n≥4 . Now, we will prove that this upper bound is tight. The bold edges of the maximal outerplanar graph illustrated in Fig. 6 can only be 2d -covered from dierent vertices, and therefore β2d(n)≥n 4 . To conclude: Theorem 10 Every n -vertex maximal outerplanar graph with n≥5 can be 2d -covered by ⌊n 4⌋ vertices. This bound is tight. Figure 6: A maximal outerplanar graph G for which β2d(G) = n 4 . References [1] P. Belleville, P. Bose, J. Czyzowicz, J. Urrutia, J. Zaks, K-vertex guarding simple polygons, Comput. Geom. Theory Appl. , 42(4) (2009), 352361. [2] J.R.S. Blair and S.B. Horton, Broadcast covers in graphs, Congr. Num. 173 (2005), 109115. [3] P. Bose, T. Shermer, G. Toussaint, and B. Zhu, Guarding Polyhedral Terrains, Computational Geometry: Theory and Applications , 6(3) (1997), 173185. [4] C.N. Campos and Y. Wakabayashi, On dominating sets of maximal outerplanar graphs, Discrete Appl.Math , 161(3) (2013), 330335. [5] Q. Chen, L. Zhao, Approximation algorithms for the L -distance vertex cover problem, Proc. ICTMF (2012), Bali, Indonesia, 100104. [6] D. Erwin, Dominating broadcasts in graphs, Bull. Inst. Combin. Appl. 42 (2004), 89105. [7] S. Fisk. A short proof of Chvatal's watchman theorem, J. Combin. Theory Ser. B , (24) (1978), 374. [8] T.W. Haynes, S.T. Hedetniemi, P.J. Slater, Fundamentals of Domination in Graphs , M. Dekker, 1998. [9] E. King, J. Pelsmajer, Dominating sets in plane triangulations, Discret Math. 310(17-18) (2010), 2221 2230. [10] L.R. Matheson, R.E. Tarjan, Dominating sets in planar graphs, Eur. J. Combin. 17(6) (1996), 565568. [11] A. Meir, J.W. Moon, Relations between packing and covering number of a tree, Pacic J. Math 61(1) (1975), 225233. [12] J. O'Rourke, Art Gallery Theorems and Algorithms , Oxford University Press, Inc., New York, USA, 1987. [13] F. Tian, J. Xu, Bounds for distance domination numbers of graphs, Journal of University of Science and Technology of China 34(5) (2004), 529534. [14] F. Tian, J. Xu, A note on distance domination numbers of graphs, Aust. J. of Combin 43 (2009), 181 190. 54