Trees With Unique Minimum

International Journal of Soft Computing, Mathematics and Control (IJSCMC), Vol. 4, No.
1, February 2015
TREES WITH UNIQUE MINIMUM

DOMINATING SETS
Sharada B
Department of Studies in Computer Science, University of Mysore, Manasagangothri,
Mysore
ABSTRACT
A set D of vertices of a graph G is a dominating set if every vertex in V \ D is adjacent to some vertex in D.
In this paper, we provide a constructive characterization of trees with unique minimum dominating set.
KEYWORDS
Dominating set, graph, tree, vertex
1. INTRODUCTION
Let G = (V, E) be a graph. The subset D of V is a dominating set if every vertex in V \ D is
adjacent to some vertex in D. The domination number of G, denoted by (G), is the minimum
cardinality of a dominating set of G. A dominating set of cardinality (G) is called a (G)-set.
The literature on domination and its variations in graphs has been surveyed and detailed in the
two books by Haynes, Hedetniemi, and Slater [1, 2]. Gunther, Hartnell, Markus, and Rall [3] have
studied graphs with unique minimum dominating sets. Later, Fishermann and L. Volkzmann [4],
made a thorough study of unique minimum domination in trees. Haynes and Henning [5] gave a
characterization for trees with unique minimum total dominating sets. Chellali et. al[6], made a
study on trees with unique minimum paired-dominating sets. Recently, Blidia et. al.[7]
characterized the trees with unique minimum locating dominating sets. We provide a constructive
characterization of trees with unique minimum dominating sets.
A graph G is called a unique minimum domination graph, or just a UMD-graph, if G has a unique
(G)-set. Observe that the path P3 has the support vertex set as its unique minimum dominating
set. A vertex of degree one is called an end vertex or a leaf and its neighbour is called a support
vertex. The set of leaves in T is denoted by L(T) and the set of support vertices by S(T). For a
vertex v the open neighborhood of v is the set N(v) and its closed neighborhood is the set N[v].
We denote Gv as G\ {v}. For notation and graph theory terminology, we in general follow [8].
2. KNOWN RESULTS
The following is an important result which guides the main results of this paper.
DOI : 10.14810/ijscmc.2015.4102
13
International Journal of Soft Computing, Mathematics and Control (IJSCMC), Vol. 4, No. 1, February 2015
Theorem 2.1:
Let T be a tree of order n 3. Then the following conditions are equivalent:
i.
T is a UMD-tree with (T)-set S.
ii.
T has a (T)-set S for which every vertex v S is a support vertex or satisfies |pn(v, S)|
2.
iii.
T has a (T)-set S for which (T - v) > (T) for every v S .
3. MAIN RESULTS
In this section we provide a constructive characterization of all UMD-trees. For this purpose we
describe a procedure for building a family of labelled trees that have unique minimum
dominating sets, as follows.
Let {T k }, k 1 be the family of trees constructed inductively such that T1 is a star K1,n, n > 1
and Tk = T, a tree. If k 2, Ti+1can be obtained recursively from Ti by the operation 1 or 2 for i
= 1, 2, ..., k 1.
We define the status of a vertex v, denoted sta(v) to be A or B. Initially if T1 = K1,n, n > 1, then
sta(v) = A if v is a support vertex and sta(v) = B, if v is a leaf. Once a vertex is assigned a status,
the status remains unchanged as the tree is constructed.
Operation 1 : Assume v T i and sta(v) = A. The tree Ti+1 is obtained from Ti by adding a star
K1,m, m > 1 with support vertex u and the edge uv. Let sta(u) = A and sta(w) = B, where w is a leaf
of K1,m.
Operation 2 : Assume v T i and sta(v) = B. The tree Ti+1 is obtained from Ti by adding a star
K1,m, m > 1 with support vertex u and the edge uv. Let v be adjacent to x in Ti. If deg(x) > 2 then u
is a support vertex of K1,m. If deg(x) = 2 then u is a leaf of K1,m. Let sta(w) = A if w is a support
vertex of K1,m and sta(w) = B, if w is a leaf of K1,m.
is closed under the two operations 1 and 2 .
For T , let A(T) and B(T) be the sets of

vertices of status A and B respectively. We have the following observations, which
follow from the construction of .
Observations 3.1:
Let T
i.
ii.
iii.
iv.
v.
and v V (T )
If sta(v) = A, then v is adjacent to at least two vertices of B(T).
If sta(v) = B, then v is adjacent to exactly one vertex of A(T).
If v is a support vertex, then sta(v) = A.
If v is a leaf, then sta(v) = B.
|A(T)| < |B(T)|.
14
Lemma 3.2:
If T , then A(T) is a (T)-set. Moreover if T is obtained from T ' , by the operation 1 or
2
then (T) = (T) + 1.
Proof:
By the Observations, it is clear that A(T) is a dominating set. Now we prove that A(T) is a (T)set. We proceed by induction on the length k of the sequence of trees needed to construct the tree
T. Suppose k = 1, then T = K1,n, n > 1, belongs to . Then by the construction of the family ,
the only vertex of sta(A) is the support vertex of the star, which dominates all the other vertices.
Hence, A(T) is a (T)-set. This establishes the base case.
Assume then that the result holds for all trees in , that can be constructed from a sequence of
fewer than k trees where k 2. Let T be obtained from a sequence T1, T2, ..., Tk of trees,
where T = Tk-1 and T = Tk. By our inductive hypothesis A(T) is a (T)-set.
We now consider two possibilities depending on whether T is obtained from T by the operation
1 or 2 .
Case 1: T is obtained from T by operation 1 .
Suppose T is obtained from T by adding a star K1,m, m > 1 with support vertex u and the edge uv,
where v T . Then sta(u) = A and sta(w) = B, where w is a leaf of K1,m. Any (T)-set can be
extended to a (T)-set by adding to it the support vertex w, which is of status A. Hence,
A ( T ) A ( T ' ) { w } is a (T)-set.
Since T is obtained from T by operation 1 , T can have exactly one more vertex of status A than
T. Since (T) = |A(T)| and (T) = |A(T)|, it follows that (T) = (T) + 1.
Case 2: T is obtained from T by operation 2 .
The proof is very similar to Case 1.
Lemma 3.3:
If T , then (T x) > (T), for every x A (T ).
Proof:
We proceed by induction on the order p of T. If p = 3 then T P3 . Let P3 be labelled as u, v,
w i.e. v is a support vertex, u and w are leaves. By previous lemma A(P3) = {v} is a (P3)-set.
Clearly, (P3 v) = 2 > 1 = (P3). This establishes the base case.
Assume that the lemma is true for T ' with |V(T)| < p. Let T = Tr be obtained from a sequence
of trees T1, T2, ..., Tr-1 = T. Since |V(T)| < |V(T)|, by induction hypothesis (Tx) > (T), for
every x A (T ' ). Two cases arise.
15
Case 1: x A (T ' ).
Any (T x)-set can be extended to a (T x)-set by adding a vertex y A ( T ) \ A ( T ' )
i .e . ( T x ) ( T ' x ) 1 . By previous lemma, (T) = (T) + 1 < (Tx) + 1 = (T x), for
every x A (T ).
Case 2: x A ( T ) \ A ( T ' )
Let T be obtained from T by adding a star K1,m, m > 1 to a vertex of T. Let x be the support
vertex of K1,m. T x contains m+1 components, hence (T x) = (T) + m = (T) 1 + m > (T),
since m > 1, as desired.
Theorem 3.4:
A tree T has the unique minimum dominating set if and only if
T .
Proof:
By lemma 3.3, it is sufficient to prove that the condition is necessary. We proceed by induction
on the order p of the tree. For p = 3, T = P3 has the unique minimum dominating set and also
T . Assume that p 4 and all trees T of order less than p, with unique minimum dominating
set belong to the family .
Let P: v1, v2, ..., vr be a longest path in T. Obviously deg(v1) = deg(vr) = 1 and v2 is a support
vertex. If it is a strong support vertex, let v2 be adjacent to the leaves l1, l2, ..., ls. Then K1,s is a star
with support vertex v2. Define T = T K1,s. If v2 is not a strong support vertex and deg(v2) = 2
define T = T \ {v1, v2, v3}. In both the cases, any (T)-set can be extended to a (T)-set by adding
the vertex v2. Hence, (T) = (T) + 1.
Since T is a UMD-tree, there exists a (T)-set S such that (T x) > (T), for every x S . Let S
= S T. Then S is a (T)-set. Let w S ' then w S and hence (T w) > (T). Therefore (T)
= (T) 1 < (T w) 1.
Any (T w)-set can be extended to a dominating set of T w by adding v1. Thus (T w)
(T w) + 1. Hence (T) <(T w) 1 (T w), for every w S . Hence T is a UMD-tree.
Since |V (T)| < |V (T)|, by the induction hypothesis T ' . Thus T is obtained from T by the
operation 1 or 2 . Hence T .
REFERENCES
[1]
[2]
[3]
[4]
[5]
Haynes T W, Hedetniemi S T & Slater P J, (1998) Fundamentals of Domination in Graphs, Marcel

Dekker, New York.
Haynes T W, Hedetniemi S T & Slater P J, (1998) (Eds.), Domination in Graphs: Advanced Topics,
Marcel Dekker, New York.
Gunther G, Hartnell B, Markus L R & Rall D, (1994) Graphs with unique minimum dominating
Sets, Congr. Numer. Vol. 101, pp55-63.
Fishermann M & Volkmann L, (2002) Unique minimum domination in trees, Aus. J. Comb. Vol.
25, pp117-124.
Haynes T W, Henning M A, (2002) Trees with unique total dominating sets, Discuss. Math. Graph
Theory, Vol. 22, pp233-246.
16
[6]
[7]
[8]
Chellali M & Haynes T W, (2004) Trees with unique minimum paired-dominating sets, Ars
Combin., Vol.25, pp3-12.
Blidia M, Chellali M, Lounes R & Maffray F, (2011) Characterizations of trees with unique
minimum locating-dominating sets, J. Combin. Math. and Combin. Comp., Vol.1, pp.23-33.
West D B (2001) Introduction to graph theory, Prentice Hall.
Authors
Sharada B received the MCA (Computer Science), M.Sc. (Mathematics), Ph.D. degree from
the University of Mysore, Mysore in 2002, 2004 and 2009 respectively. She is serving as
Assistant Professor of Computer Science at niversity of Mysore, Manaagangothri, Mysore. Her
current research interest includes Combinatorics, Graph Theory and Image Processing.
17

Trees With Unique Minimum

Uploaded by

Copyright:

Available Formats

Trees With Unique Minimum

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Trees With Unique Minimum

Uploaded by

Copyright:

Available Formats

International Journal of Soft Computing, Mathematics and Control (IJSCMC), Vol. 4, No.

TREES WITH UNIQUE MINIMUM

For T , let A(T) and B(T) be the sets of

then (T) = (T) + 1.

Haynes T W, Hedetniemi S T & Slater P J, (1998) Fundamentals of Domination in Graphs, Marcel

You might also like