Total global neighbourhood domination
A subset D of the vertex set of a connected graph G is called a total global neighbourhood dominating set (tgnd-set) of G if and only if D is a total dominating set of G as well as GN, where GN is the neighbourhood graph of G. The total global neighbourhood domination number (tgnd-number) is the min...
Saved in:
| Published in: | Algebra and Discrete Mathematics |
|---|---|
| Date: | 2017 |
| Main Authors: | , |
| Format: | Article |
| Language: | English |
| Published: |
Інститут прикладної математики і механіки НАН України
2017
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/156643 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Total global neighbourhood domination / S.V. Siva Rama Raju, I.H. Nagaraja Rao // Algebra and Discrete Mathematics. — 2017. — Vol. 24, № 2. — С. 320-330. — Бібліогр.: 8 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860255012264869888 |
|---|---|
| author | Siva Rama Raju, S.V. Nagaraja Rao, I.H. |
| author_facet | Siva Rama Raju, S.V. Nagaraja Rao, I.H. |
| citation_txt | Total global neighbourhood domination / S.V. Siva Rama Raju, I.H. Nagaraja Rao // Algebra and Discrete Mathematics. — 2017. — Vol. 24, № 2. — С. 320-330. — Бібліогр.: 8 назв. — англ. |
| collection | DSpace DC |
| container_title | Algebra and Discrete Mathematics |
| description | A subset D of the vertex set of a connected graph G is called a total global neighbourhood dominating set (tgnd-set) of G if and only if D is a total dominating set of G as well as GN, where GN is the neighbourhood graph of G. The total global neighbourhood domination number (tgnd-number) is the minimum cardinality of a total global neighbourhood dominating set of G and is denoted by γtgn(G). In this paper sharp bounds for γtgn are obtained. Exact values of this number for paths and cycles are presented as well. The characterization result for a subset of the vertex set of G to be a total global neighbourhood dominating set for G is given and also characterized the graphs of order n(≥3) having tgnd-numbers 2,n−1,n.
|
| first_indexed | 2025-12-07T18:48:10Z |
| format | Article |
| fulltext |
“adm-n4” 22:47 page #142
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 24 (2017). Number 2, pp. 320–330
© Journal “Algebra and Discrete Mathematics”
Total global neighbourhood domination
S. V. Siva Rama Raju and I. H. Nagaraja Rao
Communicated by D. Simson
Abstract. A subset D of the vertex set of a connected graph
G is called a total global neighbourhood dominating set(tgnd-set)
of G if and only if D is a total dominating set of G as well as
GN , where GN is the neighbourhood graph of G. The total global
neighbourhood domination number(tgnd-number) is the minimum
cardinality of a total global neighbourhood dominating set of G
and is denoted by γtgn(G). In this paper sharp bounds for γtgn
are obtained. Exact values of this number for paths and cycles are
presented as well. The characterization result for a subset of the
vertex set of G to be a total global neighbourhood dominating set
for G is given and also characterized the graphs of order n(> 3)
having tgnd-numbers 2, n − 1, n.
Introduction and preliminaries
Domination is an active topic in graph theory and has numerous
applications to distributed computing, the web graph and adhoc networks.
Haynes et al. gave a comprehensive introduction to the theoretical and
applied facets of domination in graphs.
A subset D of the vertex set V is called a dominating set [8] of the
graph G if and only if each vertex not in D is adjacent to some vertex
in D. The domination number γ(G) is the minimum cardinality of the
dominating set of G.
2010 MSC: 05C69.
Key words and phrases: semi complete graph, total dominating set, connected
dominating set.
“adm-n4” 22:47 page #143
S. V. S. R. Raju, I. H. N. Rao 321
Many variants of the domination number have been studied. For
instance a dominating set S of graph G is called a total dominating set [3]
if and only if every vertex in V is adjacent to a distinct vertex in D. The
total domination number of G, denoted by γt(G) is the smallest cardinality
of the total dominating set of G. A set D is called a connected dominating
set of G if and only if D is a dominating set of G and 〈D〉 is connected. The
connected domination number [4] of G, denoted by γc(G) is the smallest
cardinality of the connected dominating set of G. A dominating set D
of connected graph G is called a connected dominating setof G if the
induced subgraph 〈D〉 is connected. The connected domination number of
G, denoted by γc(G) is the least cardinality of the connected dominating
set of G [7].
If G is a connected graph, then the Neighbourhood Graph [7] of
G, denoted by N(G) (or) GN , is the graph having the same vertex
set as that of G and edge set being {uv/u, v ∈ V (G), there is w ∈
V (G) such that uw, wv ∈ E(G)} [2].
In [5], a new type of graphs, called semi complete graphs, are introduced
as follows. A connected graph G is said to be semi complete if any two
vertices in G have a common neighbour.
A subset D of the vertex set V is called a global neighbourhood domi-
nating set [6] of the graph G if and only if D is a dominating set of G, as
well as GN . The global neighbourhood domination number, γgn(G) is the
minimum cardinality of the global neighbourhood dominating set of G.
In the present paper, we introduce a new graph parameter, the total
global neighbourhood domination number, for a connected graph G. We
call D ⊆ V a total global neighbourhood dominating set(tgnd-set) of G if
and only if D is a total dominating set for both G, GN . The total global
neighbourhood domination number is the minimum cardinality of a total
global neighbourhood dominating set of G and is denoted by γtgn(G). By
a γtgn-set of G, we mean a total global neighbourhood dominating set for
G of minimum cardinality.
All graphs considered in this paper are simple, finite, undirected and
connected. For all graph theoretic terminology not defined here, the reader
is referred to [1] and [8].
In this paper sharp bounds for γtgn are given. A characterization result
for a proper subset of the vertex set of G to be a tgnd-set of G is obtained
and also characterized the graphs whose tgnd-numbers are 2, n, n − 1.
Note. If G is a simple graph such that G has isolates, then clearly γtgn-set
of G does not exist. So, unless otherwise stated, throughout this paper G
stands for a connected graph such that GN has no isolates.
“adm-n4” 22:47 page #144
322 Total global neighbourhood domination
1. Main results
We give the tgnd-numbers of some standard graphs.
Proposition 1. 1) γtgn(Kn) = 2; n = 3, 4, . . . ,
2) γtgn(C3) = 2
3) γtgn(C4) = 4
4) γtgn(Pn) = 4; n = 4, 5
5) γtgn(Pn(or)Cn) = 4[n
6 ] + j; n = 6m + j; j = 0, 1, 2, 3.
= 4[n
6 ] + 4; n = 6m + j; j = 4, 5.
6) γtgn(Km,n) = 4; m, n > 2.
7) γtgn(Sm,n) = 4.
8) γtgn(CnoK2) = n
9) γtgn(K1,n) does not exist.
Now, we give a characterization result for a total dominating set of G
to be a total global neighbourhood dominating set of G. Also, we give a
relation between connected dominating set and total global neighbourhood
dominating set.
Theorem 1. For a graph G the following holds.
(i) A total dominating set D of G is a total global neighbourhood domi-
nating set of G if and only if from each vertex in D there is a path
of length two to a vertex in D. (characterization result)
(ii) Any connected dominating set for G of cardinality atleast four is a
total global neighbourhood dominating set for G.
Proof. The proof of (i) is trivial.
The proof of (ii) is as follows. Let D ⊆ V (vertex set of G) be a
connected dominating set of G with |D| > 4. It is enough to prove that
D is a total dominating set of GN . If D = V , we are through. Otherwise,
let v be any vertex in V − D. Suppose v is adjacent to all the vertices of
D (in G). Since 〈D〉 is connected there are u, w in D such that 〈uvw〉 is
a triangle in G. This implies uv, vw are in GN (u, w are in D). If v is not
adjacent to atleast one vertex in D, since D is connected there is w in D
such that vw is in GN . Hence in either case there is a w in D such that
vw is in GN .
Let v be an arbitrary vertex in D. Since D is a connected dominating
set of G of cardinality atleast four, there is a v1 in D such that vv1 lies
on C3 (in G) or dG(v, v1) = 2. In either case vv1 is in GN .
Hence D is a total dominating set of GN .
“adm-n4” 22:47 page #145
S. V. S. R. Raju, I. H. N. Rao 323
Remark. For any connected graph G of order n > 4, we have γt(G) 6
γtgn(G) 6 γc(G).
Lemma 1. If H is a spanning subgraph of a connected graph G, then
γtgn(G) 6 γtgn(H).
Lemma 2. For a graph G with n > 1 vertices, we have 2 6 γtgn(G) 6 n.
Proof. The proof follows by the characterization result.
Now, we characterize the graphs attaining lower bound.
Theorem 2. γtgn(G) = 2 if and only if there is an edge uv in G that lies
on C3 such that any vertex in V − {u, v} is adjacent to atleast one of u, v.
Proof. Assume that γtgn(G) = 2. So there is a pair of vertices u, v in V
such that {u, v} is a total dominating set for G, GN . This implies u, v
are adjacent in G, GN . Hence uv lies on a cycle C3 = 〈uvwu〉 in G. Since
{u, v} is a total dominating set for G, for x ∈ V − {u, v}, xv or xu is an
edge in G.
The inverse implication is clear.
Now, we characterize the graphs attaining upper bound.
Theorem 3. γtgn(G) = n if and only if G = C4 or P4.
Proof. Assume that γtgn(G) = n. Suppose that diam(G) > 4. Then
dG(u, v) > 4 for some u, v in G. Clearly u or v is not a cut vertex in G.
Hence V − {u} or V − {v} is connected dominating set of cardinality
atleast four. By Theorem.1(ii), V − {u} or V − {v} is a tgnd-set of G of
cardinality n − 1, a contrary to our assumption.
Suppose that diam(G) = 3. Without loss of generality assume that
dG(u, v) = 3 for some u, v in G. Let P = 〈uv1v2v〉 be a diammetral path
in G. Form a spanning tree of G say G
′
by preserving the diammetral
path. Clearly diam(G
′
) > 3. If G
′
6= P , then V − {w} (w is a pendant
vertex in G
′
) is a tgnd-set of G
′
. By Lemma 1, V − {w} is a tgnd-set of
G of cardinality n − 1, a contrary to our assumption. If G
′
= P , then G
is not cyclic. This implies that G is tree with diameter three. Clearly G
cannot have more than two pendant vertices. Hence G = P4.
Suppose that diam(G) = 2. By hypothesis, G cannot be acyclic. Also
G cannot have pendant vertices. Therefore G is cyclic and each vertex
lies on a cycle. Suppose that g(G) = 3. If G = C3, γtgn(G) = 2 < 3 a
contradiction. If G 6= C3, then V (C3) ⊂ V . If all the vertices in V −V (C3)
“adm-n4” 22:47 page #146
324 Total global neighbourhood domination
are adjacent to C3, then γtgn(G) = 3 < n, a contrary to our assumption.
If there is atleast one vertex v4 in V − V (C3) not adjacent to C3, then
V −{v4} is a tgnd-set of G which is again a contradiction. Hence g(G) 6= 3.
Suppose that g(G) = 4. Let C4 = 〈v1v2v3v4〉 be a cycle in G. If
V = V (C4), then we have two possibilities G = C4, G 6= C4. If G 6= C4,
we have g(G) = 3 which is not possible. If G = C4, then γtgn(G) = 4(= n).
If V 6= V (C4) (i.e. V (C4) ⊂ V ). Notice that G has no pendant vertices.
Since g(G) = 4, any vertex in V − V (C4) can be adjacent to exactly two
non adjacent vertices of C4. If all the vertices in V − V (C4) are adjacent
to vertices in C4, then γtgn(G) < n, a contrary to our assumption. If
there is a vertex v5 in V − V (C4) not adjacent to C4, then V − {v5} is a
tgnd-set of G, a contrary to our assumption. Hence by our assumption
g(G) = 4 implies G = C4.
Suppose that g(G) = 5. Then we have two possibilities, G = C5,
G 6= C5. If G = C5, then γtgn(G) = 4, a contrary to our assumption. If
G 6= C5, then V = V (C5) or V 6= V (C5). If V = V (C5), then g(G) < 5
a contradiction to our supposition. If V 6= V (C5)(i.e.V (C5) ⊂ V ). Since
g(G) = 5, each vertex in V − V (C5) is adjacent to at most one vertex in
C5. If all the vertices in V − V (C5) are adjacent to C5, then V (C5) is a
tgnd-set of G, a contrary to our assumption. Suppose that there is a vertex
v7 in V − V (C5) adjacent to C5(= 〈v1v2v3v4v5v1〉). Since diam(G) = 2,
v7 is at a distance two from each vertex of C5. Then V − {v6v7} (〈v1v6v7〉
is a path) is a tgnd-set of G, a contrary to our assumption. So g(G) 6= 5.
Clearly diam(G) 6= 1. Hence we have G = C4 or G = P4. The inverse
implication is clear.
Theorem 4. If diam(G) 6= 2, 3. Then, γtgn(G) = n − 1 if and only if
G = P5 or C3.
Proof. Assume that γtgn(G) = n−1. Suppose that diam(G) > 5. Forming
a spanning tree G
′
of G, we get γtgn(G) 6 γtgn(G
′
) 6 n − m < n − 1, a
contrary to our assumption(here m is the number of pendant vertices in
G
′
). Therefore diam(G) 6 4.
Suppose that diam(G) = 4. If G = P5, then γtgn(G) = 4 = 5 − 1. If
G 6= P5, forming a spanning tree G
′
of G, we have γtgn(G) < n − 1, a
contrary to our assumption. Hence G = P5. Suppose that diam(G) = 1.
This implies G = Kn(n > 3). By Theorem 2, γtgn(G) = 2 < n − 1
whenever n > 4, a contrary to our assumption. So G = C3. The inverse
implication is clear.
“adm-n4” 22:47 page #147
S. V. S. R. Raju, I. H. N. Rao 325
Theorem 5. Suppose n > 5 and diam(G) = 2. Then, γtgn(G) = n − 1 if
and only if G = C5 or G is isomorphic to H given by
Proof. Assume that γtgn(G) = n − 1. By hypothesis g(G) 6 5. Suppose
that g(G) = 5. If G = C5, then γtgn(G) = n − 1(n = 5). If G 6= C5, then
V = V (C5) or V 6= V (C5). If V = V (C5), then g(G) < 5, a contradiction.
If V 6= V (C5) i.e., V (C5) ⊂ V . Clearly G has no pendant vertices. By
hypothesis any vertex in V −V (C5) is adjacent to atleast two non adjacent
vertices of C5 or at a distance two from each vertex of C5. From the former
case or later case we get g(G) = 4, a contradiction. So V 6= V (C5). Hence
g(G) = 5 implies G = C5.
Suppose that g(G) = 4. Then G = C4 or G 6= C4. If G = C4,
γtgn(G) = 4 = n > n − 1 a contrary to our assumption. If G 6= C4,
then we have V = V (C4) or V 6= V (C4). If V = V (C4), then g(G) = 3
a contradiction to our supposition. If V 6= V (C4) i.e., V (C4) ⊂ V . By
hypothesis and our supposition G has no pendant vertices and any vertex
v in V − V (C4) is adjacent to exactly two non adjacent vertices of C4 or
v is at a distance two from each vertex of C4 or v is at a distance two
from a vertex of C4 and adjacent to a vertex of C4, non adjacent to the
former. Except in the first case we can form a spanning tree G
′
of G with
diam(G
′
) > 5. So γtgn(G) 6 γtgn(G
′
) 6 n − m < n − 1, a contrary to our
assumption(here m is the number of pendant vertices in G
′
). If G has
more than one vertex of first kind, then γtgn(G) < n − 1 a contrary to our
assumption. If G has exactly one vertex of first kind, then γtgn(G) = n−1
and G is isomorphic to H.
Suppose that g(G) = 3. Clearly G has a cycle C3 (= 〈v1v2v3v1〉).
If G 6= C3, then V (C3) ⊂ V . Clearly G cannot have more than one
pendant vertex. Suppose G has exactly one pendant vertex, say v. Since
diam(G) = 2, there is a vertex w on C3 such that vw is in G. Without loss
of generality assume that w = v1. Clearly {v1, v2} or {v1, v3} or {v1, v}
is a tgnd-set for G a contrary to our assumption. This implies G has no
pendant vertices. So any vertex in V − V (C3) is adjacent to C3 or at a
distance two from atleast one vertex of C3. In either case γtgn(G) < n − 1.
The inverse implication is clear.
“adm-n4” 22:47 page #148
326 Total global neighbourhood domination
Theorem 6. Suppose that n > 5 and diam(G) = 3. Then γtgn(G) = n−1
if and only if G is isomorphic to H given by
Proof. Assume that γtgn(G) = n − 1. Clearly g(G) is not greater than 6.
Suppose that g(G) = 5. By hypothesis G 6= C5. This implies V (C5) ⊂
V . Clearly G cannot have more than two pendant vertices. Suppose G has
exactly one pendant vertex, say v. By hypothesis v is adjacent to a vertex
of C5(〈v1v2v3v4v5v1〉), say v1. Then clearly V −{v2, v3} is a tgnd-set of G,
a contrary to our assumption. Suppose G has exactly two pendant vertices.
Since diam(G) = 3 they are adjacent to a vertex on C5 or adjacent to
end vertices of an edge in C5. In either case γtgn(G) = n − 2 < n − 1, a
contrary to our assumption. So G cannot have pendant vertices. Since
diam(G) = 3 and g(G) = 5, G cannot have more than two cycles. Hence
g(G) 6= 5.
Suppose g(G) = 3. Clearly G 6= C3 (since n > 5). Also G cannot
have pendant vertices. If |V (G)| = 5 or all the vertices in V − V (C3) are
adjacent to C3 or there is a vertex at a distance two from C3, we get a
contrary to our assumption. Hence g(G) 6= 3.
Suppose g(G) = 4. Since diam(G) = 3, G 6= C4.Clearly G cannot have
more than two pendant vertices. If |V (G)| = 5, since diam(G) = 3 the
vertex in V −V (C4) is a pendant vertex. This implies γtgn(G) = 4 = 5−1 =
n−1. Suppose |V (G)| > 6. If all the vertices in V −V (C4) are adjacent to
C4 (each vertex in V −V (C4) can be adjacent to exactly two non adjacent
vertices in C4 (since g(G) = 4)), then γtgn(G) = 4 6 n − 2 < n − 1 a
contrary to our assumption. If not, there is atleast one vertex in V −V (C4)
at a distance two from C4 (say v). Then V − {v, v5} is a tgnd-set of G
(C4 = 〈v1v2v3v4〉, v1v5 is an edge in G) which is again a contradiction. So
|V (G)| is not greater than or equal to 6. Hence G ∼= H.
Theorem 7. Suppose g(G) = 3 and diam(G) = 2. Then γtgn(G) = n − 2
if and only if G = K4 or G ∼= K4 − {e} or G is isomorphic to H given by
“adm-n4” 22:47 page #149
S. V. S. R. Raju, I. H. N. Rao 327
Proof. Assume that γtgn(G) = n − 2. Since g(G) = 3 there is a cycle
C3 = 〈v1v2v3〉 in G. Clearly V (C3) ⊂ V . Suppose there is a vertex v in
V −V (C3) which is not adjacent to C3. Since diam(G) = 2 there are paths
of length 2 from v to each vertex of C3, say 〈vv4v1〉, 〈vv5v2〉, 〈vv6v3〉.
Case 1: v4 6= v5 6= v6. Then V − {v, v4, v5} is a tgnd-set of G.
Case 2: two of them are equal. Without loss of generality assume that
v4 = v5. Clearly G cannot have pendant vertices. Then V − {v, v4, v1} is
a tgnd-set of G.
Case 3: v4 = v5 = v6. Clearly G cannot have pendant vertices. Then
V − {v1, v2, v3} is a tgnd-set of G.
In each of the three cases, we get a contradiction with our assumption.
So our supposition is false. Hence all the vertices in V −V (C3) are adjacent
to C3. Clearly C3 has exactly one neighbour in V − V (C3), say v. If v is
adjacent to exactly one vertex of C3, then γtgn(G) = 2 = 4−2 and G ∼= H.
If v is adjacent to exactly two vertices of C3, then γtgn(G) = 2 = 4−2 and
G ∼= K4−{e}. If v is adjacent to all vertices of C3, then γtgn(G) = 2 = 4−2
and G = K4.
The inverse implication is clear.
Theorem 8. If δ(G) > 3 and g(G) > 4, then
2e − n(n − 3) 6 γtgn(G) 6 n − ∆(G) + 1.
Proof. Suppose that D is a γtgn-set of G. Since g(G) > 4, for each vertex
in V there is a vertex in D which is non adjacent to the former. This
implies e 6 nC2
− [n − γtgn] −
γtgn
2 . Hence 2e − n(n − 3) 6 γtgn(G).
Suppose dG(v) = ∆(G) for some v in V . Let NG(v) =
{v1, v2, . . . , v∆(G)}. Now consider the set D = [V − NG(v)]
⋃
{vi :
i is exactly one of 1, 2, . . . , ∆(G)}. Without loss of generality assume
that D = [V − NG(v)]
⋃
{v∆(G)}. Let u1 ∈ V .
Case 1: u1 ∈ V −D. This implies u1 ∈ {v1, v2, . . . , v∆(G)−1}. Without loss
of generality assume that u1 = v1. Clearly u1v is in G.
Case 2: u1 ∈ D. This implies u1 /∈ {v1, v2, . . . , v∆(G)−1}. If u1 = v or
u1 = v∆(G), then u1v∆(G) or u1v is in G. If not since δ(G) > 3 and
g(G) > 4 there is u2 /∈ {v, v1, v2, . . . , v∆(G)} such that u1u2 is in G. Hence
D is a total dominating set of G.
We now show that D is a total dominating set of GN . Let u1 ∈ V .
Case 1: u1 ∈ V − D. This implies u1 ∈ {v1, v2, . . . , v∆(G)−1}. Since
dG(vi, v∆(G)) = 2, i = 1, 2, . . . , ∆(G) − 1 we have viv∆(G) is in GN . So
v1, v∆(G) is in GN .
“adm-n4” 22:47 page #150
328 Total global neighbourhood domination
Case 2: u1 ∈ D. This implies u1 /∈ {v1, v2, . . . , v∆(G)−1}. Suppose u1 = v.
Since δ(G) > 3 and g(G) > 4 we have vu2 is in GN . for some u2 ∈ N(N(v))
and u2 ∈ D. If u1 = v∆(G). Suppose u1 /∈ {v, v1, v2, . . . , v∆(G)}.If u1 ∈
N(vi) for some i = 1, 2, . . . , ∆(G), then u1v is an edge in GN . If u1 /∈ N(vi)
for any i.
Subcase a: u1 ∈ N(N(vi)) for some i = 1, 2, . . . , ∆(G). Without loss of
generality assume that u1 ∈ N(N(vi)). Since δ(G) > 3, there are u2 and
u3 in G, adjacent to u1. Since g(G) > 4, u2 and u3 cannot be adjacent to
{v1, v2, . . . , v∆(G)}. This implies there is u4 in D such that u2u4 or u3u4
is in G. Hence u1u4 is in GN .
Subcase b: u1 ∈ V −[{N(N(vi)) : i=1, 2, . . . , ∆(G)}
⋃
{v1, v2, . . . , v∆(G)}].
By hypothesis there is a u2 in D − {v, v∆(G)} such that u1u2 is in GN . D
is a total dominating set of GN .
Hence D is a tgnd-set of G whose cardinality is n − ∆(G) + 1. So
γtgn(G) 6 n − ∆(G) + 1. This completes the proof.
Notation. For n > 4 and k = 2, 3 define a family of graphs Gk as follows.
G ∈ Gk if and only if there is D ⊂ V such that |D| = k satisfying:
(i) 〈D〉 is connected;
(ii) at least two vertices of D lie on the same C3;
(iii) each vertex in V − D is adjacent to a vertex in D.
Theorem 9. For n > 4, γtgn(G) = 3 if and only if G ∈ G3 − G2.
Proof. Assume that γtgn(G) = 3. Then there is a γtgn-set of G such that
|D| = 3 and 〈D〉 is connected. By the characterization result for tgnd-set
there is a path of length 2 between a pair of adjacent vertices in D. This
implies at least two vertices of D lie on the same C3. So G ∈ G3. Since
D is a γtgn-set, G ∈ G2. Hence G ∈ G3 − G2. The inverse implication is
clear.
Before considering the next result, for convenience we introduce the
following. For n > 6, define a family of trees Tk as T ∈ Tk if and only if
there is a D ⊂ V with |D| = k satisfying:
(i) 〈D〉 is connected in G;
(ii) each vertex in V − D is adjacent to a vertex in D (in G).
Theorem 10. γtgn(T ) = 4 if and only if T ∈ T4 − T3.
Proof. Suppose γtgn(T ) = 4. Then there is a γtgn − set of T (say D) such
that D satisfies (i) and (ii) of the above mentioned family. This implies
“adm-n4” 22:47 page #151
S. V. S. R. Raju, I. H. N. Rao 329
T ∈ T4. Clearly by characterization theorem T /∈ T3. Hence T ∈ T4 − T3.
The inverse implication is clear.
Theorem 11. γtgn(T ) = 5 if and only if T ∈ T5 − T4.
Theorem 12. If G is a graph satisfying the following two conditions:
(i) each edge of G lies on C3 or C5;
(ii) there is no path of length four between any pair non adjacent vertices
in G,then
γt(G) + γt(G
N )
2
6 γtgn(G) 6 γt(G) + γt(G
N )
Proof. By the hypothesis, we have G = GNN . Clearly γt(G) 6 γtgn(G),
γt(G
N ) 6 γtgn(GN ) = γtgn(G). Hence γt(G)+γt(GN )
2 6 γtgn(G). Clearly
γtgn(G) 6 γt(G) + γt(G
N ). Thus the result follows.
Theorem 13. Assume that D is a γt-set of G. If there is a v in V − D
adjacent to all the vertices in D, then γtgn(G) 6 1 + γt(G).
Proof. Clearly D
⋃
{v} is a tgnd-set of G. Hence, the theorem follows.
Theorem 14. If G is a semi complete graph, then D ⊆ V is a total
dominating set of G if and only if D is a tgnd-set of G.
Proof. The proof follows from the fact that each edge in a semi complete
graph lies on C3.
Theorem 15. If G is a semi complete graph, then a set D ⊆ V with
δG(〈D〉) > 1 is a global dominating set of G if and only if D is a tgnd-set
of G.
Proof. The proof follows from the fact that, for a semi complete graph G,
we have Gc = GN .
References
[1] Bondy J.A. and Murthy, U.S.R., Graph theory with Applications, The Macmillan
Press Ltd (1976).
[2] D.F. Rall, Congr.Numer., 80 (1991), 89–95.
[3] E.J. Cockayne,et al., Total domination in graphs, Networks, 10 (1980), 211-219.
[4] E. Sampathkumar, H.B. Walikar,The connected Domination Number of a Graph,
J. Math.Phy. Sci, 13 (1979), 607–613.
“adm-n4” 22:47 page #152
330 Total global neighbourhood domination
[5] I.H. Naga Raja Rao, S.V. Siva Rama Raju, On Semi Complete Graphs, International
Journal of Computational Cognition, Vol.7(3), (2009),50–54.
[6] I.H. Naga Raja Rao, S.V. Siva Rama Raju, Global Neighbourhood Domination,
Proyecciones Journal of Mathematics, Vol.33(1), 2014.
[7] R.C. Brigham, R.D. Dutton, On Neighbourhood Graphs, J. Combin. Inform. System
Sci., 12, (1987), 75–85.
[8] Teresa W. Haynes, et al., Fundamentals of dominations in graphs, Marcel Dekker,
Inc., New York–Basel.
Contact information
S. V. Siva Rama
Raju
Academic Support Department, Abu Dhabi
Polytechnic, Al Ain, United Arab Emirates;
Department of Information Technology, Ibra col-
lege of Technology, Ibra, Sultanate of Oman
E-Mail(s): venkata.sagiraju@adpoly.ac.ae,
shivram2006@yahoo.co.in
I. H. Nagaraja Rao Laxmikantham Institute of Advanced Studies,
G.V.P. College of Engineering, Visakhapatnam,
India
E-Mail(s): ihnrao@yahoo.com
Received by the editors: 19.10.2015
and in final form 06.11.2015.
|
| id | nasplib_isofts_kiev_ua-123456789-156643 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1726-3255 |
| language | English |
| last_indexed | 2025-12-07T18:48:10Z |
| publishDate | 2017 |
| publisher | Інститут прикладної математики і механіки НАН України |
| record_format | dspace |
| spelling | Siva Rama Raju, S.V. Nagaraja Rao, I.H. 2019-06-18T18:19:40Z 2019-06-18T18:19:40Z 2017 Total global neighbourhood domination / S.V. Siva Rama Raju, I.H. Nagaraja Rao // Algebra and Discrete Mathematics. — 2017. — Vol. 24, № 2. — С. 320-330. — Бібліогр.: 8 назв. — англ. 1726-3255 2010 MSC:05C69. https://nasplib.isofts.kiev.ua/handle/123456789/156643 A subset D of the vertex set of a connected graph G is called a total global neighbourhood dominating set (tgnd-set) of G if and only if D is a total dominating set of G as well as GN, where GN is the neighbourhood graph of G. The total global neighbourhood domination number (tgnd-number) is the minimum cardinality of a total global neighbourhood dominating set of G and is denoted by γtgn(G). In this paper sharp bounds for γtgn are obtained. Exact values of this number for paths and cycles are presented as well. The characterization result for a subset of the vertex set of G to be a total global neighbourhood dominating set for G is given and also characterized the graphs of order n(≥3) having tgnd-numbers 2,n−1,n. en Інститут прикладної математики і механіки НАН України Algebra and Discrete Mathematics Total global neighbourhood domination Article published earlier |
| spellingShingle | Total global neighbourhood domination Siva Rama Raju, S.V. Nagaraja Rao, I.H. |
| title | Total global neighbourhood domination |
| title_full | Total global neighbourhood domination |
| title_fullStr | Total global neighbourhood domination |
| title_full_unstemmed | Total global neighbourhood domination |
| title_short | Total global neighbourhood domination |
| title_sort | total global neighbourhood domination |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/156643 |
| work_keys_str_mv | AT sivaramarajusv totalglobalneighbourhooddomination AT nagarajaraoih totalglobalneighbourhooddomination |