Total Dominating Color Transversal Number of Graphs And Graph Operations

International Journal of Mathematics and Statistics Invention (IJMSI)
E-ISSN: 2321 – 4767 P-ISSN: 2321 - 4759
www.ijmsi.org Volume 4 Issue 5 || June. 2016 || PP-45-48
www.ijmsi.org 45 | Page
Total Dominating Color Transversal Number of Graphs And
Graph Operations
D.K.Thakkar1
and A.B.Kothiya2
1
Department Of Mathematics, Saurashtra University, Rajkot
2
G.K.Bharad Institute Of Engineering, Kasturbadham, Rajkot
ABSTRACT : Total Dominating Color Transversal Set of a graph is a Total Dominating Set of the graph
which is also Transversal of Some 𝜒 - Partition of the graph. Here 𝜒 is the Chromatic number of the graph.
Total Dominating Color Transversal number of a graph is the cardinality of a Total Dominating Color
Transversal Set which has minimum cardinality among all such sets that the graph admits. In this paper, we
consider the well known graph operations Join, Corona, Strong product and Lexicographic product of graphs
and determine Total Dominating Color Transversal number of the resultant graphs.
Keywords: Domination number, Total Domination number, Total Dominating Color Transversal number
AMS Subject classification code (2010): 05C15, 05C69
I. Introduction
We begin with simple, finite, connected and undirected graph without isolated vertices. We know that proper
coloring of vertices of graph G partitions the vertex set V of G into equivalence classes (also called the color
classes of G). Using minimum number of colors to properly color all the vertices of G yields χ equivalence
classes. Transversal of a χ - Partition of G is a collection of vertices of G that meets all the color classes of the χ
– Partition. That is, if T is a subset of V( the vertex set of G) and {V1, V2, ...., Vχ} is a χ - Partition of G then T
is called a transversal of this χ - Partition if T ∩ Vi ≠ ∅, ∀ i ∈ {1, 2,...., χ }. Motivated by work of R.L.J.
Manoharan in [12], we introduced the introduced the concept of Total Dominating Color Transversal Set of
graphs in [1]. It is a collection of vertices of a graph G that is a Total Dominating Set of the graph with extra
property that it is transversal of some χ – Partition of the graph. Let us first see some definitions.
II. Definitions
Definition 2.1[3]: (Dominating Set)
Let G = (V, E) be a graph. Then a subset S of V (the vertex set of G) is said to be a Dominating Set of G if for
each v ∈ V either v ∈ S or v is adjacent to some vertex in S.
Definition 2.2[3]: (Minimum Dominating Set/ Domination number)
Let G = (V, E) be a graph. Then a Dominating Set S is called the Minimum Dominating Set of G if S =
minimum { D : D is a Dominating Set of G}. In such case S is called a γ – Set of G and the cardinality of S is
called Domination number of the graph G denoted by γ (G) or just by γ.
Definition 2.3[4]: (Total Dominating Set) Let G = (V, E) be a graph. Then a subset S of V (the vertex set of G)
is said to be a Total Dominating Set of G if for each v ∈ V, v is adjacent to some vertex in S.
Definition 2.4[4]: (Minimum Total Dominating Set/Total Domination number) Let G = (V, E) be a graph.
Then a Total Dominating Set S is said to be a Minimum Total Dominating Set of G if S = minimum { D : D is
a Total Dominating Set of G}. Here S is called γt
−set and its cardinality, denoted by γt
(G) or just by γt
, is
called the Total Domination number of G.
Definition 2.5[1]: (𝛘 -partition of a graph) Proper coloring of vertices of a graph G, by using minimum
number of colors, yields minimum number of independent subsets of vertex set of G called equivalence classes
(also called color classes of G). Such a partition of a vertex set of G is called a χ - Partition of the graph G.
Definition 2.6[1]: (Transversal of a 𝛘 - Partition of a graph) Let G = (V, E) be a graph with χ – Partition {V1,
V2, ....., Vχ}. Then a set S ⊂ V is called a Transversal of this χ – Partition if S ∩ Vi≠ ∅, ∀ i ∈ {1, 2, 3, ...., χ}.

Total Dominating Color Transversal number of Graphs and Graph Operations
Definition 2.7[1]: (Total Dominating Color Transversal Set) Let G = (V, E) be a graph. Then a Total
Dominating Set S ⊂ V is called a Total Dominating Color Transversal Set of G if it is Transversal of at least one
𝛘 – Partition of G.
Definition 2.8[1]: (Minimum Total Dominating Color Transversal Set/Total Dominating Color
Transversal number) Let G = (V, E) be a graph. Then S ⊂ V is called a Minimum Total Dominating Color
Transversal Set of G if S = minimum { D : D is a Total Dominating Color Transversal Set of G}. Here S is
called γtstd
−Set of G and its cardinality, denoted by γtstd
(G) or just by γtstd
, is called the Total Dominating
Color Transversal number of G.
Definition 2.9[12]: (Join of Graphs) The Join of simple graphs G & H, written G ⋁ H, is the graph obtained
from the disjoint union of their vertex sets by adding the edges{ uv : u ∈ V (G), v ∈V(H)}.
Definition 2.10[12]: (Corona of Graphs) Let G and H be two graphs. The corona G ◦ H is a graph formed from
a copy of G and |V (G)| copies of H by joining the i-th vertex of G to every vertex in the i-th copy of H. (V (G)
is the vertex set of G)
Definition 2.11[2]: (Strong Product of Graphs)
The Strong product G ⊠ H of graphs G and H is the graph with vertex set V (G)×V (H) and edge set {{(u, x),
(v, y)} | u = v and x is adjacent to y in H or u is adjacent to v in G and x = y or u is adjacent to v in G and x is
adjacent to y in H}.
Definition 2.12[2]: (Lexicographic Product of Graphs)
The Lexicographic product G[H] of graphs G and H is the graph with vertex set V (G)×V (H) and edge set {{(u,
x), (v, y)} | u = v and x is adjacent to y in H or u is adjacent to v in G}.
III. Main Results
Theorem 3.1 [1]: If 𝛄𝐭(G) = 2 then 𝛄𝐭𝐬𝐭𝐝(G) = 𝛘 (G). (G may be disconnected)
Theorem 3.2: If G and H are two graphs then 𝛄𝐭𝐬𝐭𝐝 (G ∨ H) = 𝛘 (G) + 𝛘 (H).
Proof: We know that χ (G ∨ H) = χ (G) + χ (H). According to the definition of Join of graphs, γt
(G ∨ H) = 2.
So by theorem 3.1, γtstd
(G ∨ H) = χ (G ∨ H). So γtstd
(G ∨ H) = χ (G) + χ (H).
Theorem 3.3: If G and H are two graphs. If V (G) is the vertex set of graph G then
𝛄𝐭𝐬𝐭𝐝 (G ∘ H) = |V (G)|, when 𝛘 (H) ≤ 𝛘 (G)
|V (G)| + 𝛘 (H) – 𝛘 (G), when 𝛘 (H) > 𝛘 (G).
Proof: Case 1. χ (H) ≤ χ (G)
Since each vertex of G is adjacent to all the vertices of some copy of H, the vertex set of G will form a γt
−set
of G ∘ H and as χ (H) ≤ χ (G), this set will also be a γtstd
- Set of G ∘ H. So γtstd
(G ∘ H) = |V (G)|.
Case 2. χ (H) > χ (G)
As in case 1, the vertex set of G will be γt
−set of G. This set together with χ (H) – χ (G) vertices of H will a
γtstd
- Set of G ∘ H. So γtstd
(G ∘ H) = |V (G)| + χ (H) – χ (G).
Example 3.4:
C6 ∘ K2
Fig. 1 γtstd (C6 ∘ K2) = 6

Now let us consider the strong product of graphs. First we mention one useful remark about this product.
Remark 3.5: 1) G ⊠ H ≅ H ⊠ G.
2) By [8], If G and H have at least one edge,
χ (G ⊠ H) ≥ max { χ (G), χ (H)}+ 2 and by [9], χ (G ⊠ H) ≥ χ (G) + ω (H),
where ω (H) is the clique number of H.
3) By [10], If G has at least one edge, χ (G ⊠ H) ≥ χ (G) + 2 ω (H) -2, where
ω (H) is the clique number of H.
4) E (G × H) ∪ E (G□H) = E (G ⊠ H).
Theorem 3.6: If G and H are two graph then 𝛄𝐭𝐬𝐭𝐝(G ⊠ H) ≥ 4.
Proof: We first note that G and H are two connected graphs with δ (G) ≥ 1 and with δ (H) ≥ 1.
χ (G ⊠ H) ≥ max { χ (G), χ (H)}+ 2 implies χ (G ⊠ H) ≥ 4. Hence γtstd
(G ⊠ H) ≥ 4.
Theorem 3.7: Let G and H be two graphs. If 𝛄𝐭𝐬𝐭𝐝(G ⊠ H) = 4 then both G and H are bipartite.
Proof: Given that γtstd
(G ⊠ H) = 4. So χ (G ⊠ H) ≤ 4. But as χ (G ⊠ H) ≥ 4, χ (G ⊠ H) = 4. Now 4 = χ (G
⊠ H) ≥ max { χ (G), χ (H)}+ 2 implies that χ (G) = χ (H) = 2.
Theorem 3.8: If G and H are two graphs with 𝛄 (G) = 𝛄(H) = 1 then 𝛄𝐭𝐬𝐭𝐝 (G ⊠ H) = 𝛘 (G ⊠ H).
Proof: Let {a} and {b} be, respectively, Dominating Sets of G and H. So {(a, b)} is a dominating set of G ⊠ H.
So γ (G ⊠ H) = 1. So γt
(G ⊠ H) = 2. So by theorem 3.1, γtstd
(G ⊠ H) = χ (G ⊠ H).
Corollary 3.9: 𝛄𝐭𝐬𝐭𝐝 (Km ⊠ Kn) = mn.
Proof: Obviously, as Km ⊠ Kn is a complete graph with mn vertices.
Now we consider the Lexicographic product of graphs. Consider the following remark.
Remark 3.10: 1) Lexicographic product is non- commutative.
2) E (G ⊠ H) ⊂ E(G[H]).
3) By [11] If G has at least one edge, then for any graph H,
χ (G[H]) ≥ χ (G) + 2 χ (H) – 2.
Theorem 3.11: If G and H are two graph then 𝛄𝐭𝐬𝐭𝐝(G[H]) ≥ 4.
Proof: χ (G[H]) ≥ χ (G ⊠ H) ≥ 4, we obtain γtstd
(G[H]) ≥ 4.
Theorem 3.12: Let G and H be two graph. If 𝛄𝐭𝐬𝐭𝐝 (G[H]) = 4 then both G and H are bipartite graphs.
Proof: We first note that G and H are two connected graphs with δ (G) ≥ 1 and with δ (H) ≥ 1. Let γtstd
(G[H])
= 4. Then χ (G[H]) = 4. So 4 = χ (G[H]) ≥ χ (G) + 2 χ (H) – 2, which implies that χ (G) = χ (H) =2.
Theorem 3.13: If G and H are two graphs with 𝛄 (G) = 𝛄 (H) = 1 then 𝛄𝐭𝐬𝐭𝐝 (G[H]) = 𝛘 (G[H]).
Proof: As E(G ⊠ H) ⊂ E(G[H]) and γ (G ⊠ H) = 1, we obtain γ (G[H]) = 1. So γt
(G[H]) = 2 and hence by
theorem 3.1, γtstd
(G[H]) = χ (G[H]).
Corollary 3.14: 𝛄𝐭𝐬𝐭𝐝 (Km[Kn]) = mn.
Proof: Obviously, as Km[Kn] is a complete graph with mn vertices.
References
[1] D. K. Thakkar and A. B. Kothiya, Total Dominating Color Transversal number of Graphs, Annals of
Pure and Applied Mathematics, Vol. 11(2), 2016, 39 – 44.
[2] Wilfried Imrich & Sandi Klavzar, „„ Product graphs‟‟ , John Willey & Sons, INC.
[3] T. W. Haynes, S. T. Hedetniemi, and P. J. Slater, Fundamentals of domination in graphs, Marcel
Dekker, NewYork, 1998.
[4] Michael A. Henning and Andres Yeo, Total Domination in Graphs, Springer, 2013.
[5] Douglas B. West (Second Edition), „„Introduction to Graph Theory‟‟, Pearsen Education, INC.., 2005.
[6] R. Balakrishnan and K. Ranganathan, “A Textbook of Graph Theory, Springer”, New York, 2000.
[7] Goksen BACAK, “ Vertex Color of a Graph”, Master of Science Thesis, ˙IZM˙IR, December, 2004.
[8] K. Vesztergombi, “ Some remarks on the Chromatic number of Strong Product of Graphs”,Acta

Cybernet,4 (1978/79) 207 – 212.
[9] P.K.Jha, “ Hypercubes, Median graphs and Product of graphs: Some Algorithmic and Combinatorial
results”, Ph.D. Thesis, Iowa state Uni., 1990.
[10] Sandi Klavzar and Uros Milutinovic, “ Note – Strong Product of Kneser Graphs”, University of
Maribor PF, Koroska 160 62000 Maribor, Slovenia.
[11] Sandi Klavzar, “Coloring Graph Products – A survey”, Elsevier Discrete Mathematics 155 (1996), 135
– 145.
[12] R. L. J. Manoharan, Dominating colour transversals in graphs, Bharathidasan University, September,
2009.

Total Dominating Color Transversal Number of Graphs And Graph Operations

Recommended

More Related Content

What's hot (19)

Viewers also liked (20)

Similar to Total Dominating Color Transversal Number of Graphs And Graph Operations (20)

Recently uploaded (20)

Total Dominating Color Transversal Number of Graphs And Graph Operations