![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
Abstract
In this paper, we study graphs which possess an independent point-set dominating set (in short, ipsd-set). We call such a graph as an ipsd-graph. We first provide general structural characterization of separable ipsd-graphs and thereafter, in our quest to characterize such graphs, we establish that girth of an ipsd-graph is at most 5. We further characterize ipsd-graphs with girth 5 and -free ipsd-graphs of girth 4. Then, we exhibit a class of ipsd-graphs with girth
containing
as an induced subgraph and in the process, we introduce a new graph equivalence relation termed as duplicated equivalence.
1 Introduction
For standard terminology and notation in graph theory, as also for pictorial representations of graphs, we refer the standard text-books such as F. Harary Citation[1] and Chartrand Citation[2]. For domination related concepts we refer the book by Haynes et al. Citation[3,4]. Further, unless mentioned otherwise, graphs will be assumed to be finite and connected.
For any given graph , we will denote the vertex set of
by
(or simply
) and edge set of
by
(or
). The neighborhood of a vertex
in a graph
, denoted by
, is the set of all vertices in
adjacent with the vertex
. The set
is the closed neighborhood of vertex
in
and is denoted by
. The distance
between two vertices
and
of graph
is the length of shortest path joining them. The diameter of
is given by
. A cycle of length
will be called an
-cycle. If
is a separable graph, then the set of all non-trivial blocks of
will be denoted by
.
E. Sampathkumar and Pushpa Latha Citation[5] in 1993 defined a set to be a point-set dominating set (or in short psd-set) of graph
if for every non-empty subset
of
there exists a vertex
such that the induced subgraph
is connected. This definition can be seen as a natural extension of the concept of domination (cf. Citation[3,4]) by using the interpretation that a subset
of the vertex set
of
is a dominating set if and only if for every singleton subset
of
, there exists a vertex
in
such that the induced subgraph
is connected.
Though point-set domination as a concept was introduced purely from theoretical interest, it can be applied to many real life situations. One such real life context where the notion of point-set domination can be noticed is discussed in Citation[6] when a set () of supervisors amongst the employees in a business organization (
) is needed to be identified so that each group (
) of workers amongst the rest (
) forms a task group under the leadership of at least one of the supervisors (say
) irrespective of hierarchical relationships (adjacencies) existing within the group of workers—the task group so formed may be visualized as the set
. Obviously, this task group needs to be connected in order that each individual in the group be “relevant” in relation to others in the group towards its collective performance of the task(s).
Another motivation to study point-set domination is discussed in Citation[7] which is inspired from the facility location application of domination (cf. Citation[3]), where we want that for any chosen area (set of vertices) there should exist a station providing facility for the whole area.
Definition 1.1
A subset of the vertex set
of graph
is a point-set dominating set (or in short psd-set) of graph
if for every non-empty subset
of
there exists a vertex
such that the induced subgraph
is connected.
Definition 1.2
Citation[8] A set in a graph
is an independent set if
is totally disconnected. The independence number
of
is the maximum cardinality among all independent sets of G.
Note that some authors use (cf. Citation[9]) instead of
to represent independence number.
Definition 1.3
A set in a graph
is an independent point-set dominating set (or in short an ipsd-set) of graph
if
is independent and point-set dominating set of
.
In domination theory, by a well known result of Berge [Citation10], every maximal independent set in a graph is an independent dominating set of
. Hence every finite graph has an independent dominating set. However, as noted in Citation[5,6], a graph may or may not possess an independent point-set dominating set. Thus the study of graphs possessing an ipsd-set is an important problem in the theory of point-set domination in graphs.
Definition 1.4
A graph is said to be an ipsd-graph if it has an independent point-set dominating set (or psd-set), otherwise it will be referred to as a non-ipsd graph.
In Citation[5], it was proved that there does not exist any independent psd-set in a graph with diameter greater than or equal to .
Proposition 1.5
Citation[5] If a connected graph possesses an independent psd-set, then its diameter does not exceed
.
However, the condition is not sufficient and the cycle is such an example. The diameter of the cycle
is
and yet it does not possess an ipsd-set. Thus it is interesting to characterize graphs having independent psd-sets. The following are some useful results on ipsd-graphs.
Proposition 1.6
Citation[5] Let be a psd-set of a graph
and
. Then
.
Proposition 1.7
Citation[6] A graph has an independent psd-set if there exists a vertex
such that
is independent.
Proposition 1.8
Citation[6] If is a separable ipsd-graph and
is an ipsd-set of
such that
for every
, then there exists a cut vertex
such that
. In particular, in this case
is independent.
Theorem 1.9
Citation[6] A tree has an independent psd-set if and only if
.
Theorem 1.10
Citation[6,11] Every independent point-set dominating set of a graph is a minimal point-set dominating set.
Acharya and Gupta Citation[6,12] made an extensive study on the problem of determining graphs which possess an independent psd-set (or an ipsd-set). In particular, they studied structure of separable graphs admitting ipsd-sets by classifying the set of all independent psd-sets of a separable graph
into three classes as follows:
For a separable graph , if
and
is such that
, then in [Citation13], it was noted that
may or may not be an ipsd-set of
. On this basis, the set
was further partitioned into two subclasses:
Thus
Acharya and Gupta then obtained structural characterization of separable graphs admitting ipsd-set of each type separately.
Theorem 1.11
Citation[6] For any separable graph with
,
if and only if
and if
, then
1: |
| ||||
2: |
|
Theorem 1.12
Citation[6] For any separable graph ,
if and only if
and if
, then
can be partitioned into three non-empty subsets
and
satisfying following properties:
1: |
| ||||
2: |
| ||||
3: |
|
Theorem 1.13
Citation[6] For any separable graph ,
if and only if
and if
, then
1: |
| ||||
2: | for each |
Theorem 1.14
Citation[6] For any separable graph with
,
if and only if there exists a cut vertex
in
such that
1: |
| ||||
2: |
| ||||
3: | if |
These theorems provide structural information of separable graphs possessing ipsd-sets. But, in general, the problem of characterizing graphs containing independent psd-sets is still open. In fact, it was noted by Acharya and Gupta in Citation[6] that characterizing an ipsd-graph containing a triangle and/or pentagon is one of the most important unsolved problems in this area of the theory of domination in graphs.
Further, since any graph can be embedded as an induced subgraph into a graph containing independent psd-sets by adding a new vertex in
adjacent to all the vertices of
, it is not possible to obtain a necessary and sufficient condition involving forbidden subgraphs that characterizes graphs containing an independent psd-set.
In this paper, we extend the work done by Acharya et al. in Citation[6,11–17] on point-set domination, in particular, the work in Citation[6] by focusing on the girth and circumference of ipsd-graphs.
The following observations on the distance of vertices in an ipsd-graph will be useful for further study on ipsd-graphs.
Observation 1.15
Let be an ipsd-set of a graph
and
be any two vertices.
(a) | If | ||||
(b) | If | ||||
(c) | If | ||||
(d) | If |
Since our focus is on girths of ipsd-graphs, the following result due to Min-Jen Jou Citation[8] will be helpful.
Theorem 1.16
Citation[8] For cycle with
,
2 General results on IPSD graphs
In this section, we proceed with our investigation on graphs possessing an independent point-set dominating set (in short, ipsd-set). We first provide general structural characterization of separable ipsd-graphs.
Theorem 2.1
Let be a separable graph with
. Then
is an ipsd-graph if and only if exactly one of the following two conditions hold:
(i) |
| ||||||||||||||||||||||
(ii) |
|
Proof
Let be an ipsd-graph and
be an ipsd-set of
. We have three cases:
Case I. for some
.
Then and
. If
, then condition (i)(a) follows from Theorem 1.11 and we are done.
If , then
and
can be partitioned into three non-empty subsets
and
satisfying the conditions of Theorem 1.12. Then any vertex
is a cut vertex in
and satisfies (i) (b).
Case II. for some
.
Then . From Theorem 1.13,
and
A |
| ||||
B | for each |
Then it is easy to see that any vertex , satisfies the condition (i)(b).
Case III. contains vertices of different blocks.
Then . From Theorem 1.14, if
, then (i)(b) is satisfied and if
(ii) is satisfied.
Conversely, suppose either condition (i) or (ii) holds. If (i)(a) is satisfied, then forms an ipsd-set of
. If (i)(b) or (ii) is satisfied, then
forms an ipsd-set of
. Thus in either case
is an ipsd-graph.□
Next is an immediate but important consequence of the above theorem.
Corollary 2.2
If is an ipsd separable graph, then every block of
is an ipsd-block.
Proof
Follows immediately from Theorem 2.1(b).□
Another interesting result can be derived for triangle free separable ipsd-graphs having at least two non-trivial blocks from Theorem 2.1.
Corollary 2.3
If is a triangle free ipsd separable graph with
, then
is
-free.
Proof
Since , by Theorem 2.1, there exists a cut vertex
such that
is an independent set in
. Suppose
is not
-free graph, then there exists
such that
is an induced subgraph of
. As
is triangle free, there exist adjacent vertices
such that
for
. Then
, a contradiction to the fact that
is an independent set. Thus
is
-free.□
It is important to note that neither of the conditions i.e., being triangle free or having at least two non-trivial blocks can be dropped, otherwise separable ipsd-graph might fail to be -free. For example the graphs
and
in are both ipsd-graphs but fail to be
-free. The graph
is triangle free but have a unique non-trivial block. While the graph
has two non-trivial blocks but has
as a subgraph.
Next, we proceed to prove that girth of an ipsd-graph is less than or equal to .
Theorem 2.4
If is an ipsd graph, then
Proof
Let be an ipsd-graph such that
and
be an ipsd-set of
. Let
be any
-cycle in
. From Theorem 1.16,
, it follows that
. If
, then there exist vertices
such that
. As
is an ipsd-set, there exists a vertex
such that
But then we get a cycle in
of length less than or equal to
, a contradiction to minimality of
. Thus
. Consequently,
,
and
is an independent subset of
.
Since is independent, there exists
such that
. But then
contains a
-cycle, again a contradiction to the minimality of
. Hence our assumption is wrong and
. □
The condition in Theorem 2.4 is necessary but it is not sufficient. There exist graphs with girth less than or equal to that are not
graphs. In fact the graph in is a graph with girth
and yet is not an ipsd graph.
This result provides a new direction to the problem of characterizing ipsd-graphs. As trees are already characterized, the problem of characterizing ipsd-graphs narrows down to considering ipsd graphs of girth 3,4 and , which we tackle in the sections to follow.
3 Classes of IPSD graphs
In this section, we characterize ipsd-graphs of girth and thereafter, present few classes of ipsd-graphs of girth
and
. We first introduce following definition and notations.
Definition 3.1
[Citation18] To subdivide an edge means to delete
, add a vertex
and then join
to the end vertices of
(when
is a link, this amounts to replacing
by a path of length two). Any graph derived from a graph
by a sequence of edge subdivisions is called a subdivision of
or a
-subdivision.
Notation 3.2
For any positive integer , we denote by
, the graph obtained by subdividing each edge of a hamiltonian cycle of complete graph
exactly once (see ).
Theorem 3.3
A -connected graph
with girth
is an ipsd graph if and only if
is isomorphic to either
or
.
Proof
Let be an ipsd-graph and
be an ipsd set of
. Let
be a
-cycle in
. Since
is independent,
.
Claim 1. .
If , then for
, there exists
such that
. Hence
contains
-cycle, a contradiction. If
, w.l.o.g we can assume that
, then for the independent set
in
there exists
such that
. But, in that case,
contains either
or
, a contradiction. Thus
. Let
.
Claim 2. .
Suppose or
. W.l.o.g assume that
. Then there exists
. Since
is an ipsd-set, for the independent set
in
, there exists
such that
. Then
, a contradiction. Thus
.
Consequently, since , we must have
and
.
Claim 3. and
.
First we show that for each
. Let, if possible, there exists
such that
. As girth of
is
and
,
and
. Then it is easy to see that there exists
such that
is an independent set. Since
is psd-set, there exists
such that
. Then
, a contradiction. Thus
for each
.
Next we show that for all
. Since
,
. W.l.o.g assume that
. Then there exists
such that
. If
, then
, a contradiction. Thus
. If
, then there exists
such that
. Therefore,
, a contradiction. Thus
for all
.
Finally we proceed to prove our claim that . Suppose on the contrary, there exist distinct vertices
. Then
. Obviously,
and
are not adjacent, for otherwise,
. Since
is a psd-set, there exists
such that
. But in that case
, a contradiction. Hence our assumption is wrong and
.
Let . Then
and as
is an ipsd-set, there exist
such that
and
. Now to prove that
, observe that for each set
such that
, there exists
such that
. Thus to avoid a
-cycle in
, we must have
. Hence
and the necessity follows.
Conversely, suppose either or
. If
, then any maximal independent set of
is an ipsd-set. If
, then the set consisting of all vertices of degree
in
is an ipsd-set of
. Thus in either case graph
is an ipsd-graph.□
Remark 3.4
It is interesting to note that every -set of
is an ipsd-set of
, while in case of
, there is unique ipsd-set consisting of all vertices of degree
, which also happens to be unique
-set of
.
Next we characterize separable ipsd-graphs of girth . As noted in Corollary 2.2, if
is a separable ipsd-graph of girth
, then every block of
must be an ipsd-block. From Theorem 2.4, every block of
must be of girth
. Further, as every triangle free ipsd-graph having at least two non-trivial is
-free (Corollary 2.3), the graph
must have a unique non-trivial block isomorphic to either
or
.
Theorem 3.5
Let be a separable graph with girth 5. Then
is an ipsd graph if and only if the following conditions hold:
(a) |
| ||||
(b) | every vertex in |
Proof
Let be an ipsd-graph. Since
,
is not
-free, hence from Corollary 2.3, it follows that
has unique non-trivial block (say)
. As
is an ipsd-graph, from Corollary 2.2,
is an ipsd-block in
. Consequently, from Theorem 3.3,
is isomorphic to either
or
. Since
or
, there does not exist any vertex
such that
is independent. Consequently from Theorem 2.1,
has an ipsd-set
and
consists of pendant vertices with their supports lying in
. Let
be the set of all support vertices in
. Since
or
and
is an ipsd-set of
, it is easy to see that
is an
-set of
. Consequently,
is an
-set of
. As
, all the three conditions (a), (b) and (c) follow.
Conversely, assume that (a), (b) and (c) are satisfied. Then it is easy to see that the set forms an ipsd-set for graph
. Hence the theorem.□
Remark 3.6
Since and
, from Remark 3.4 and Theorem 3.5, for any ipsd-graph
of girth
,
where
is the unique block of
and
is the number of pendant vertices in
.
Having characterized ipsd-graphs of girth , we proceed to characterize ipsd-graphs of girth
. Again since girth
graphs are triangle free graphs, from Corollary 2.3 and Theorem 2.4, every block of an ipsd-graph of girth
is an ipsd-block of girth
. In view of Theorem 2.1, to have complete information about ipsd-graphs of girth
, it is enough to characterize
-connected ipsd-graphs of girth
. Moreover, if
is an ipsd-graph of girth
having at least two non-trivial blocks, then every block of
is
-free ipsd-block of girth
. Thus to achieve our objective, we first consider
-connected
-free ipsd-graphs with
.
Theorem 3.7
Let be a
-connected
-free graph with
. Then
is an ipsd-graph if and only if one of the following holds:
1. | There exists | ||||
2. | There exist non-adjacent vertices |
Proof
For the sufficient part, observe that if (1) is satisfied, then from Proposition 1.7, is an ipsd-graph. If (2) holds, then
is an ipsd-set of graph
.
Now to prove necessary part, let be an ipsd-graph and
be an ipsd set of
. If
satisfies condition (1), then we are through. Therefore let condition (1) is not satisfied.
Claim 1. There exists a cycle of length
such that two non-adjacent vertices of
are in
.
Since , there exists a cycle
of length
in
. If two non adjacent vertices of
are in
, then
is the required cycle and we are done with our claim. Thus let
be such that
. Since (1) is not satisfied, there exist adjacent vertices
. Since
is independent, both
and
cannot be in
. If both
and
are in
, then as
and
is ipsd-set, there exists
such that
for each
. If
, then
, a contradiction to the fact that
. But then
, again a contradiction as
is
-free. Thus exactly one of
and
is in
.
Without loss of generality, assume that and
. Since
, there exists
in
such that
. Since
is
-connected, there exists
. Clearly,
and
are non-adjacent. For otherwise,
, a contradiction. If
, then
, contradiction. Thus
. Now
is an independent subset of
, therefore there exists
such that
. If
, then
such that two non adjacent vertices
and
of the cycle are in
. If
, then
and
. Hence the claim.
Let be the cycle of length
and
. Let
and
.
Claim 2. and
,
are independent sets.
Suppose there exists such that
. Since
and
, therefore
. Since
is an independent set in
, there exists
such that
. But then
, contradiction. Hence
.
If be two adjacent vertices, then
, contradiction. Hence
is independent set. If
is not independent, there exist two adjacent vertices
. Since
, there exists
such that
for each
. But then
, a contradiction. Hence
is independent.
Claim 3. and
,
for some
.
Since is ipsd-set and
,
are independent sets in
, there exists
such that
and
. Suppose there exists
and
such that
and
are not adjacent. As
is ipsd-set, there exists a vertex
such that
. But then
, a contradiction. Thus
. Since
,
. If
, then
for any
, contradiction. Thus
. Similarly,
.
Claim 4. For any either
or
.
Since , therefore
. Let
be any vertex. Then
. Consequently,
. If
and
, then
, contradiction. Thus either
or
. Hence the condition (2) holds. Therefore necessity part follows. □
From Theorems 2.1 and 3.7, following theorem on separable -free ipsd-graphs of girth
can be easily obtained.
Theorem 3.8
Let be a
-free separable graph with girth
. Then
is an ipsd-graph if and only if exactly one of the following holds:
(i) |
| ||||||||||||||||
(ii) |
|
Having characterized -free ipsd-graphs
with
, what can we say about ipsd-graphs of girth
containing an induced subgraph isomorphic to
? In what follows we make a partial answer to this question by focusing on circumference of ipsd-graphs.
Note that circumference of an ipsd-graph of girth is either
or
. But in case of ipsd-graphs of girth
, for any positive integer
, there always exists an ipsd-graph of girth
having circumference greater than
. In fact, for an instance, for any integer
, the graph
(see ) obtained from wheel
by subdividing each edge of the cycle
of
is an ipsd-graph of girth
and circumference
.
If we consider 2-connected ipsd-graphs with girth and circumference
, then we have its complete structural information. Thus giving partial information about graphs with girth
containing an induced 5-cycle. But before characterizing such graphs, we introduce an equivalence relation on graphs using the notion of duplicate vertices Citation[8].
Definition 3.9
Citation[8] Two vertices and
(need not be distinct) in a graph
are said to be duplicated if
.
If vertices and
are duplicated in
, then we say that
and
are duplicates of each other. By definition, every vertex is a duplicate vertex of itself. It is evident that the concept of duplicate vertices in a graph
partitions the vertex set
into disjoint equivalence classes. For a vertex
in graph
, let
denote the equivalence class containing the vertex
. It is interesting to note that each equivalence class is an independent set. Also, for any graph
,
for all
.
Notation 3.10
For any graph and any vertex
, let
.
Observation 3.11
If and
are adjacent vertices of degree
in a graph
, then
and
if and only if
.
Proof
Suppose and
and let
and
. Then
,
and
. Since degree of each vertex
is
, therefore
. Hence the necessity. Sufficient part is trivial. □
Definition 3.12
Vertex Identification [Citation18] To identify non-adjacent vertices and
of a graph
is to replace these vertices by a single vertex adjacent to all the vertices which were adjacent in G to either
or
.
Definition 3.13
-Duplicate We will call a graph
to be duplicate of graph
or
-duplicate if
can be obtained from
by identifying all vertices in each degree-
equivalence class of duplicate vertices.
Note that if a graph is duplicate of graph
, then
can be treated as a subgraph of
. In that case,
for all
and
where
is the set of all duplicate vertices of
in
.
Definition 3.14
Duplicated Equivalent Two graphs and
will be called duplicated equivalent if there exists a graph
such that both
and
are
-duplicate. If
is duplicated equivalent to
, then we will denote it as
. It is easy to see that the relation
is an equivalence relation on graphs.
Lemma 3.15
A -connected graph
is
duplicated if and only if either
or there exists an induced subgraph
of
isomorphic to
and an
-set
of
such that
.
Proof
Let be
duplicated. If
, then we have nothing to prove. Let
, then as
, there exists an induced subgraph
of
isomorphic to
such that
Let . Then
for some
. W.l.o.g assume that
. Since
,
. Consequently,
. Thus
If both and
are non-empty set, then
, which contradicts Observation 3.11. Hence at least one of
and
is an empty set. W.l.o.g assume that
. Then
. Hence the necessity. Sufficiency is trivial.□
Theorem 3.16
Let be a 2-connected graph with girth
and circumference
, then
is an ipsd-graph if and only if
and
.
Proof
Let be an ipsd-graph girth
and circumference
. Trivially,
. In view of Lemma 3.15, to prove necessity, we need to show the existence of an induced subgraph
of
isomorphic to
and an
-set
of
such that
.
Since circumference and girth
,
has an induced subgraph isomorphic to
. Let
be any induced
-cycle in
. Let
be an ipsd-set of
. Since
is independent,
.
Claim: .
Suppose, on the contrary, . W.l.o.g assume that
. Then
and
are independent sets in
. Since
is an ipsd-set and
, there exist two distinct vertices
such that
and
. But then
is a 6-cycle in
, contradiction to the fact that
. Thus
.
W.l.o.g we assume that . Two cases arise:
Case 1. i.e.,
Claim 1: or
.
On the contrary, let and
. As
,
and
is an ipsd-set,
and
must be adjacent vertices. But then
forms a 6-cycle, contradiction. Hence either
or
.
W.l.o.g assume that .
Claim 2: .
Let, if possible, there exists . But then as
is an independent subset of
,
and
, we arrive at a contradiction due to the fact that
is an ipsd-set. Hence
.
Thus . As
is
-free,
is an independent set and every vertex in
has degree
. Hence
. Thus, from Lemma 3.15,
is
-duplicated.
Case 2. i.e.,
.
Claim 1: .
Suppose, on the contrary, there exists . As
and
is
-free, there exist non-adjacent vertices
. Again, as
is
-free,
. W.l.o.g we can assume that
. Since
is an independent set in
, there exists
such that
. If
, then
is a 6-cycle in
, contradiction. If
, there exists
such that
. Since
is
-free,
. Consequently,
is a 7-cycle in
, a contradiction. Hence
.
Claim 2: .
Let, if possible, there exists . As
is
-free and
,
. W.l.o.g assume that
. Since
, there exists
. If
, then
is a 6-cycle, a contradiction. Hence
. Then
is an independent set in
and therefore there exists
such that
. But then
is a 7-cycle, yielding a contradiction. Hence our assumption is wrong and
.
Claim 3: for all
.
On the contrary, let such that
. Let
. As
, w.l.o.g assume that
and
. If
, then
is a 7-cycle in
, a contradiction. If
, then there exists
such that
. But then
is a 7-cycle in
, again a contradiction. Hence
and
(as
is
-free) for all
.
Subcase I.
In this case ,
and
for every
. It follows from Lemma 3.15 that
is
-duplicated.
Subcase II.
Since , there exists
. Then
and either
or
. W.l.o.g we assume that
. Then
is a 5-cycle in
having two vertices in
. By interchanging the roles of
and
, from Case 1, it follows that
and
.
Claim: .
Since for every
and
is a dominating set, therefore
. Further, since
is
-connected
-free graph,
. It follows that
and every vertex in
has degree
.
Next we claim that . Suppose, on the contrary, there exists
such that
. Then
and for any
, the cycle
is a 7-cycle in
, contradiction. Thus
.
Observe that and
. Thus
and hence
is
-duplicated.
Conversely, suppose and
, then by Lemma 3.15, there exists an induced 5-cycle
in
such that
, where
is a maximal independent set in
. Then it is evident that
is an ipsd-set of
. Hence
is an ipsd-graph.□
Remark 3.17
If is duplicated equivalent to
and
is an induced
-cycle in
such that
, then
In fact, the collection is the set of all maximal independent sets in
. Moreover,
is also the set of all ipsd-sets of
.
The following theorem characterizes separable ipsd-graphs with girth and circumference
.
Theorem 3.18
Let be a separable graph with girth
and circumference
, then
is an ipsd-graph if and only if the following conditions hold:
(a) |
| ||||
(b) | every vertex in |
Proof
Suppose is an ipsd-graph. Since
and
,
is triangle free but not
-free. From Corollary 2.3,
has a unique non-trivial block (say)
. Then from Corollary 2.2,
is an ipsd-block of
. Obviously, girth of
is
and circumference of
is
. Consequently, from Theorem 3.16,
and
. Then there does not exist any
such that
is an independent set. Hence from Theorem 2.1,
has an ipsd-set
and
consists of pendant vertices with their supports lying in
. As noted in Remark 3.17, every ipsd-set of
is an
-set of
. Hence the necessity follows.
For the sufficiency, observe that the set forms an ipsd-set of
. Hence
is an ipsd-graph.□
4 Concluding remarks
In this paper, we first proved that girth of an ipsd-graph is always less than equal to and thereafter, characterized ipsd-graphs with girth
. We could characterize
-free ipsd-graphs of girth
. Also, using the graph equivalence relation, duplicated equivalence, we exhibited a class of ipsd-graphs of girth
having
as an induced subgraph. But the general problem of characterizing ipsd-graphs of girth
having
as an induced subgraph is still open.
Problem 1
Characterize ipsd-graphs of girth containing
as an induced subgraph.
Also, we are yet to explore ipsd-graphs of girth and it would be interesting to characterize them. As we have seen in case of separable ipsd-graphs of girth
, that characterizing separable graphs boils down to the problem of characterizing
-connected ipsd-graphs. Thus to tackle the problem of characterizing ipsd-graphs of girth
, one must first consider
-connected ipsd-graphs of girth
.
Problem 2
Characterize -connected ipsd-graphs of girth
.
In this paper, we introduced a graph equivalence relation, called duplicated equivalent. In Lemma 3.15, we presented equivalence class of w.r.t duplicated relation. It would be interesting to find equivalence classes of various other well known graphs. In [Citation19], graph equations (w.r.t graph equivalence relation for isomorphism) for line graphs, total graphs, middle graphs and quasi-total graphs were solved. Similar graph equations w.r.t duplicated equivalence relation can be considered.
Problem 3
Under what condition a graph pair is a solution to the following equation:
where
and
represent line graph, middle graph, total graph and quasi-total graph, respectively, of graph
.
References
- HararyFrank, Graph Theory1969Addison-Wesley Publishing Co.Reading, Mass.-Menlo Park, Calif.-Londonix+274
- ChartrandG.LesniakL., Graphs & Digraphsfourth ed.2005Chapman & Hall/CRCBoca Raton, FLviii+386
- HaynesT.W.HedetniemiS.T.SlaterP.J., Fundamentals of Domination in Graphs1998Marcel Dekker, Inc.New Yorkxii+446
- HaynesT.W.HedetniemiS.T.SlaterP.J., Domination in Graphs-Advanced Topics1998Marcel Dekker, Inc.New Yorkxiv+497
- SampathkumarE.Pushpa LathaL., Point-set domination number of a graph Indian J. Pure Appl. Math. 24 4 1993 225–229
- AcharyaB.D.GuptaPurnima, On point-set domination in graphs ii: Independent psd-sets J. Comb. Inf. Syst. Sci. 22 2 1997 133–148
- ZelinkaBohdan, Point-set domatic numbers of graphs Math. Bohem. 124 1 1999 77–82
- JouMin-Jen, Characterization of graphs with equal domination numbers and independence numbers Taiwanese J. Math. 14 4 2010 1537–1542
- BollobasB., The independence ration of regular graphs Proc. Amer. Math. Soc. 831981 433–436
- BergeC., Graphs and Hypergraphs1973North HollandAmsterdam
- GuptaPurnimaSinghRajeshArumugamS., Characterizing minimal point set dominating sets AKCE Int. J. Graphs Comb. 132016 283–289
- AcharyaB.D.GuptaPurnima, On point-set domination in graphs ii: Quest to characterize blocks containing independent psd-sets Nat. Acad. Sci. Lett. 23 11 2000 171–176
- AcharyaB.D.GuptaPurnima, On point-set domination in graphs ii: Minimum psd-sets AKCE J. Graphs. Comb. 2 2 2005 87–98
- AcharyaB.D.GuptaPurnima, On point-set domination in graphsBujurkeN.M.Proc. Nat. Symposium on Recent Trends in Mathematics1996Karnatak University PressDharwad
- AcharyaB.D.GuptaPurnima, On point-set domination in graphs iv: Separable graphs with unique minimum psd-sets Discrete Math. 1951999 1–13
- GuptaPurnimaJainDeepti, Global 2-point set domination number of a graph Electron. Notes Discrete Math. 532016 213–224
- GuptaPurnimaGoyalAlkaSinghRajesh, Point-set domination in graphs. viii: Perfect and efficient psd sets Lecture Notes in Comput. Sci. 103982017 300–304
- BondyJ.A.MurtyU.S.R.Graph TheoryGraduate Texts in Mathematics vol. 2442008SpringerNew Yorkxii+651
- SastryD.V.S.RajuB.S.P., Graph equations for line graphs, total graphs, middle graphs and quasi-total graphs Discrete Math. 481984 113–119