Abstract
A set is a 2-point set dominating set (2-psd set) of a graph if for any subset , there exists a non-empty subset containing at most two vertices such that the induced subgraph is connected. In this paper we characterize minimal 2-psd sets for a general graph. Based on the structure we examine 2-psd sets in a separable graph and discuss the criterion for a 2-psd set to be minimal.
1 Introduction
By a graph we mean a finite, undirected, connected and non-trivial graph with neither loops nor multiple edges. The order and the size of are denoted by and respectively. For graph theoretic terminology we refer to Harary [Citation1] and West [Citation2]. The open neighborhood of any vertex in is and closed neighborhood of in is . For a set the open (closed) neighborhood of in is and is defined as .
Definition 1.1
[Citation3]
A set is a dominating set of a graph if for every vertex in , there exists a vertex such that is adjacent to . The domination number of is the minimum cardinality of a dominating set of .
Definition 1.2
[Citation4]
A set is a set dominating set of a graph if for every set , there exists a non-empty set such that the induced subgraph is connected. The set domination number of is the minimum cardinality of a set dominating set of .
In [Citation5], Sampathkumar and Pushpa Latha introduced the concept of point set domination which is a special case of set domination.
Definition 1.3
[Citation5]
A set is a point set dominating set (or in short, psd-set) of a graph if for every subset there exists a vertex such that the induced subgraph is connected. The point set domination number of is the minimum cardinality of a point set dominating set of .
Point-set domination has been studied further by Acharya and Gupta [Citation6,Citation7]. In this paper we consider another special case of Set-domination, namely, 2-point set domination which is defined as follows.
Definition 1.4
[Citation8]
A set is a 2-point set dominating set (or in short, 2-psd set) of a graph if for every subset there exists a non-empty set containing at most two vertices such that the induced subgraph is connected.
The set of all 2-psd sets of is denoted by .
The following theorem is immediate from the definition of 2-point set dominating set and we will be using this result frequently throughout the paper.
Theorem 1.5
A subset is a -psd set of a graph if and only if for every independent set there exists a set such that is connected.
Proof
The condition is necessary by definition. Conversely, let be any subset of and let be a maximal independent subset of . Then there exists a set such that and is connected, which in turn implies that is connected. □
Clearly, every point set dominating set of is a 2-point set dominating set and every 2-point set dominating set is a dominating set of . However, the converse of the above implications is not true.
We observe that point-set domination and 2-point set domination are superhereditary properties. Hence a 2-psd set (psd-set) is minimal if and only if is not a 2-psd set (psd-set) for all . The main focus of this paper is the characterization of minimal 2-psd sets.
2 Minimal 2-psd sets in a graph
We first give a characterization of minimal 2-psd sets of a general graph.
Theorem 2.1
A -psd set of a graph is minimal if and only if for every one of the following holds:
(a) | . |
(b) | There exists an independent subset such that for every and for any two distinct vertices with , and are non-adjacent and . |
Proof
Let be a minimal 2-psd set of and let . Then is not a 2-psd set of . If is not dominated by , then . Now suppose is dominated by . Since is not a 2-psd set of , there exists an independent subset such that for all with , the induced subgraph is not connected. Hence it follows that for all . Now, let and suppose . Let . If both or both , then or is an - path in . Suppose and . If , then is an - path in . If , then where , is an - path in . Hence is connected which is a contradiction. Thus if , then and .
Conversely, suppose that for every either (i) or (ii) holds. If (i) holds, then is not a dominating set of . If (ii) holds, then for the subset , the induced subgraph is disconnected for all with or . Hence, is not a 2-psd set of , so that is a minimal 2-psd set. □
We now proceed to consider the problem of characterizing minimal 2-psd sets in separable graphs. The structure of the graph leads to specific and explicit characterization of minimal 2-psd sets. We consider separately 2-psd sets for which is contained in a single block or contained in union of all blocks at a particular cut-vertex and the remaining cases and obtain necessary and sufficient conditions for minimality for each of the cases.
Theorem 2.2
Let be a -psd set of a separable graph of order and let . Then is a minimal -psd set of if and only if and is the set of all pendant vertices of .
Proof
Let . Suppose is a minimal 2-psd set of . If there exist two adjacent vertices , then either or is a 2-psd set of which is a contradiction. Hence is independent and . The converse is obvious. □
Theorem 2.3
Let be a separable graph and let be a -psd set of such that and for some block of . Then is a minimal -psd set of if and only if for every one of the following holds:
(i) | for some block and the cut-vertex belongs to . |
(ii) | and . |
(iii) | There exists an independent set such that for any and if for some , then and . |
Proof
Let be a minimal 2-psd set of and let . Let for some block and suppose does not satisfy condition (i). This implies . Since is not a 2-psd set of , there exists an independent set such that for any and if for some , then and . Thus satisfies condition (iii). Similarly we can prove that, if and does not satisfy condition (ii), then satisfies condition (iii).
Conversely, let each satisfy one of the conditions (i), (ii) and (iii). We shall show that is minimal. Let . If satisfies condition (i) then for any , does not contain any - path and therefore, is not a 2-psd set of . If satisfies condition (ii), then is not a dominating set and hence is not a 2-psd set of . If satisfies condition (iii), then for the independent set , there does not exist any such that and is connected. Thus is not a 2-psd set of . Hence is minimal. □
Theorem 2.4
Let be a separable graph and let be a -psd set of such that for some block of . Then is a minimal -psd set of .
Proof
Let . Since , for some block . Choose a vertex such that . Then for there does not exist any set such that and is connected. Thus is not a 2-psd set for any and hence is minimal. □
In Theorems 2.2, 2.3 and 2.4 we have obtained a characterization of minimal 2-psd sets of a separable graph for which is contained in a block of . We now proceed to characterize minimal 2-psd sets for which contains vertices from more than one block. For any cut-vertex , let denote the set of all blocks of containing . For the rest of the paper stands for a 2-psd set of a separable graph for which contains vertices from more than one block.
Proposition 2.5
Let be a separable graph and let be a cut vertex of . Let be a -psd set of such that . Then all vertices of are contained in one component of .
Proof
Suppose contains vertices of different components of . Let and be two different vertices of lying in two different components of and let . Since any - path contains vertex and , there does not exist a subset such that and is connected. Hence is not a 2-psd set of , which is a contradiction. □
Proposition 2.6
Let be a -psd set of a separable graph such that for some cut-vertex . Then for all blocks except possibly for one block.
Proof
Let for some block . Suppose . Let , where and . If is not adjacent to , then which is a contradiction. Thus, every vertex of where and is adjacent to . □
Theorem 2.7
Let be a -psd set of a separable graph such that for some cut-vertex . Then is a minimal -psd set of if and only if .
Proof
Suppose is a minimal 2-psd set of . If , then is a 2-psd set of which contradicts the minimality of . Hence .
Conversely, Suppose . We shall show that is a minimal 2-psd set of . If not, there exists such that is a 2-psd set of . Choose two vertices belonging to two different blocks of . We consider three cases:
Case I: is adjacent to both and .
In this case is a cycle containing vertices of different blocks of , which is a contradiction.
Case II: is adjacent to but not to .
Now, for the set there exists such that and is connected. Since , it follows that . Now, let be a - path in . Then is a cycle containing vertices of different blocks of , which is a contradiction.
Case III: is adjacent to neither nor .
For the subsets and , there exist such that and and are connected. Now all - paths pass through and hence . This implies that , which contradicts our assumption that .
Thus there does not exist any such that is a 2-psd set of and hence is a minimal 2-psd set. □
Theorem 2.8
Let be a -psd set of a separable graph such that for any cut-vertex of . Let be a cut-vertex of such that , and for some block . Then can be partitioned into four subsets and where , and . Further, is a psd set of .
Proof
Since , is non-empty. We now prove that is non-empty. Let and . For the set , there exists a set such that and is connected. Since belong to two different blocks of , by Proposition 2.5, . Also there exists such that and is a path in . This proves that is non-empty.
We now claim that is a psd-set of . Let be an independent subset of and . Since is a 2-psd set of , there exists a set , such that and is connected. Since the vertices of and belong to two different blocks of , . Also no vertex of is adjacent to and hence there exists such that and is connected. Hence is a psd set of . Now,
Hence,
We illustrate the above theorem by a graph in . Consider the 2-psd sets and of . The corresponding pairs for of subsets of such that is a psd-set of are ; and respectively.
Theorem 2.9
Let be a -psd set of a separable graph such that for some cut-vertex . Let be such that and . Then is a minimal 2-psd set of if and only if the following are true:
(a) | . |
(b) | For every , there exists an independent set such that for any . |
(c) | For every at least one of the following holds:
|
Proof
Suppose is a minimal 2-psd set of . Since , we have . Suppose . Then is also a 2-psd set of which contradicts the minimality of 2-psd set of . Thus, . This proves condition (a).
Now suppose (b) is not true. Therefore there exists a vertex such that every independent set is contained in for some . Let and let be any independent subset of . Then and . Since is a psd-set of , there exists a vertex such that . Also since condition (b) is not true for , . Thus, is connected. Hence is a 2-psd set of which contradicts the minimality of . This proves condition (b).
Now suppose condition (c) is not true for some . Then is adjacent to some vertex of and for every independent set , there exists such that . Let and let be an independent set. If , then since is a psd-set of , there exists such that is connected. Now if , then since condition (c)(ii) is not true, there exists a such that is connected. Thus is a 2-psd set of which contradicts the minimality of . This proves condition (c).
Conversely, suppose conditions (a),(b) and (c) are satisfied. Suppose there exists such that is a 2-psd set of . We consider two cases:
Case I: .
Let . Since and belong to two different blocks of , every - path must pass through . Since, , . Also, and . Hence which in turn implies that which is a contradiction.
Case II: .
Since , or . Suppose . Let be an independent subset of and let . Since is a 2-psd set of , there exists , such that and is connected. Since the vertices of and are from different blocks of , . Since is an independent subset of there exists a vertex such that and . It is true for every independent subset of which contradicts condition (b).
Suppose . We claim that . Let . Since is a 2-psd set of , there exists a set such that and is connected. Since and belong to different blocks of , and again since is not adjacent to , for some . This shows that . Hence . Thus condition (c)(i) does not hold.
Now let be an independent subset in and let . Since is a 2-psd set of , there exists a set such that and is connected. Since , . Further, since , for some and . Hence condition (c)(ii) does not hold.
Thus in all cases we get a contradiction. Hence is a minimal 2-psd set. □
Theorem 2.10
Let be a -psd set of a separable graph such that for any cut-vertex . Then there exists a pair of adjacent cut-vertices and of such that .
Proof
Since for any cut-vertex , there exist such that and and the blocks and have no common cut-vertex.
Consider the set . Since is a 2-psd set of , there exists a set such that and is connected. Since blocks and have no common cut-vertex, . Let . Then is a path in . Since and belong to two different blocks with no common cut-vertex, and are cut vertices and are adjacent.
We claim that . Let be such that . Since is a 2-psd set of , for the set , there exists a subset such that and is connected. Since every - path passes through and , . Since and is connected, is adjacent to either or . Without loss of generality we may assume that . Now for the set , there exists a set such that and is connected. Since , . Therefore, there exists a - path not containing which is a contradiction. Thus .
Hence . □
Theorem 2.11
Let be a -psd set of a separable graph such that for any cut-vertex . Then is minimal if and only if for a pair of adjacent cut-vertices and in .
Proof
Suppose is a minimal 2-psd set of . By Theorem 2.10, for a pair of adjacent cut-vertices and in . If then is a 2-psd set of which contradicts the minimality of . Hence .
Conversely, Suppose is a 2-psd set of such that for a pair of adjacent cut vertices . Suppose there exists such that is a 2-psd set of . Let . Choose vertices and . Since , . Since and are non-adjacent vertices in , there exists a set such that and is connected. Let be the - path in . Since every - path passes through and , . Thus, and .
Now, three cases arise:
Case I: is adjacent to both and .
In this case is a cycle containing vertices of different blocks of which is a contradiction.
Case II: is adjacent to and not to .
For the set there exists such that and is connected. Since , . Now, let be a - path in . Then is a cycle containing vertices of different blocks of which is a contradiction.
Case III: is adjacent to neither nor .
Then is an independent set in . Therefore there exists such that and is connected. Since , . Let be a - path in . Then is a cycle in which is a contradiction to the fact that and are in different blocks of .
Thus in all cases is not a 2-psd set of and hence is a minimal 2-psd set. □
Notes
Peer review under responsibility of Kalasalingam University.
References
- F. Harary, Graph Theory, Addison-Wesley, Reading, Massachusetts, 1969
- West D.B. Introduction To Graph Theory 1996 Prentice Hall Inc. New Jersey
- Haynes T. Hedetniemi S.T. Slater P.J. Fundamentals of Domination in Graphs 1998 Marcel Dekker New York
- Sampathkumar E. Pushpa Latha L. Set domination in graphs J. Graph Theory 18 5 1994 489 495
- Sampathkumar E. Pushpa Latha L. Point-set domination number of a graph Indian J. Pure Appl. Math. 24 4 1993 225 229
- Acharya B.D. Gupta P. On Point-Set Domination in Graphs II: Minimum PSD-Sets AKCE J. Graphs Comb. 2 2 2005 87 98
- Acharya B.D. Gupta P. On point set somination in graphs IV: Separable graphs with unique minimum PSD-sets Discrete Math. 195 1–3 1999 1 13
- Gupta Purnima Acharya Mukti Jain Deepti 2-Point set domination number of a cactus Gulf J. Math. 4 3 2016 80 89