Colour class domination numbers of some classes of graphs
We compute the colour class domination number of fan graphs, double fan graphs, Helm graphs, flower graphs and sun flower graphs.
Збережено в:
| Дата: | 2014 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2014
|
| Назва видання: | Algebra and Discrete Mathematics |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/153323 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Colour class domination numbers of some classes of graphs / Y. Venkatakrishnan, V. Swaminathan // Algebra and Discrete Mathematics. — 2014. — Vol. 18, № 2. — С. 301–305. — Бібліогр.: 7 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-153323 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1533232019-06-15T01:26:59Z Colour class domination numbers of some classes of graphs Venkatakrishnan, Y. Swaminathan, V. We compute the colour class domination number of fan graphs, double fan graphs, Helm graphs, flower graphs and sun flower graphs. 2014 Article Colour class domination numbers of some classes of graphs / Y. Venkatakrishnan, V. Swaminathan // Algebra and Discrete Mathematics. — 2014. — Vol. 18, № 2. — С. 301–305. — Бібліогр.: 7 назв. — англ. 1726-3255 2010 MSC:05C15, 05C69. http://dspace.nbuv.gov.ua/handle/123456789/153323 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
We compute the colour class domination number of fan graphs, double fan graphs, Helm graphs, flower graphs and sun flower graphs. |
| format |
Article |
| author |
Venkatakrishnan, Y. Swaminathan, V. |
| spellingShingle |
Venkatakrishnan, Y. Swaminathan, V. Colour class domination numbers of some classes of graphs Algebra and Discrete Mathematics |
| author_facet |
Venkatakrishnan, Y. Swaminathan, V. |
| author_sort |
Venkatakrishnan, Y. |
| title |
Colour class domination numbers of some classes of graphs |
| title_short |
Colour class domination numbers of some classes of graphs |
| title_full |
Colour class domination numbers of some classes of graphs |
| title_fullStr |
Colour class domination numbers of some classes of graphs |
| title_full_unstemmed |
Colour class domination numbers of some classes of graphs |
| title_sort |
colour class domination numbers of some classes of graphs |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2014 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/153323 |
| citation_txt |
Colour class domination numbers of some classes of graphs / Y. Venkatakrishnan, V. Swaminathan // Algebra and Discrete Mathematics. — 2014. — Vol. 18, № 2. — С. 301–305. — Бібліогр.: 7 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT venkatakrishnany colourclassdominationnumbersofsomeclassesofgraphs AT swaminathanv colourclassdominationnumbersofsomeclassesofgraphs |
| first_indexed |
2025-07-14T04:30:17Z |
| last_indexed |
2025-07-14T04:30:17Z |
| _version_ |
1837595274909843456 |
| fulltext |
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 18 (2014). Number 2, pp. 301–305
© Journal “Algebra and Discrete Mathematics”
Colour class domination numbers
of some classes of graphs
Yanamandram B. Venkatakrishnan, V. Swaminathan
Communicated by D. Simson
Abstract. We compute the colour class domination number
of fan graphs, double fan graphs, Helm graphs, flower graphs and
sun flower graphs.
1. Preliminaries
Let G = (V, E) be a graph, with the number of vertices |V (G)| = n.
By the neighbourhood of a vertex v of G we mean the set NG(v) = {u ∈
V (G) : uv ∈ E(G)}. We say that a vertex is isolated if it has no neighbour,
while it is universal if it is adjacent to all other vertices. The degree of a
vertex v, denoted by dG(v), is the cardinality of its neighbourhood. Let
δ(G) mean the minimum degree among all vertices of G.
A vertex of a graph is said to dominate itself and all of its neighbors.
A subset D ⊆ V (G) is a dominating set of G if every vertex of G is
dominated by at least one vertex of D. The domination number of G,
denoted by γ(G), is the minimum cardinality of a dominating set of G.
For a comprehensive survey of domination of graphs, the reader is referred
to [3, 4].
A proper colouring of a graph G = (V, E) is an assignment of colours
to the vertices of the graph, such that any two adjacent vertices have
different colours. The chromatic number χ(G) is the minimum number
2010 MSC: 05C15, 05C69.
Key words and phrases: colour class domination number, Helm graph, sun
flower graph, double fan graph.
302 Colour class domination numbers
of colours needed in a proper colouring of G. By a χ−partition of G, we
mean the partition {V1, V2, · · · , Vχ} of V (G) where each Vi is the colour
class representing the colour i, i = 1, 2, · · · , χ.
Dominating and colouring concepts have nice interactions, one such
combination is the dominator colouring introduced by Gera et al. A
dominator colouring of a graph G is a proper colouring in which each
vertex of graph dominates every vertex of some colour class. The dominator
chromatic number χd(G) is the minimum number of colour classes in a
dominator colouring of a graph G. Swaminathan et al [6] relaxed the
condition of ‘every vertex dominating a colour class’ with ‘every colour
class is dominated by a vertex of G’ and defined a new parameter colour
class domination number of a graph G. A colour class domination partition
of a graph G is a proper colouring in which vertices in every colour
class is dominated by a vertex in V (G). The colour class domination
number χcd(G) is the minimum number of colour classes in a colour
class domination partition of a graph G. It is to be noted that dominator
chromatic number and colour class domination number are not comparable.
The domination colouring of some classes of graphs was found in [2,5] and
the colour class domination number of middle graph and center graph of
K1,n, Cn and Pn was calculated in [7]. In the present paper, we find the
colour class domination number of fan graphs, double fan graphs, helm
graphs, flower graphs and sun flower graphs.
2. Main results
We recall from [6] the following result.
Theorem 1. For a graph G, max{χ(G), γ(G)} 6 χcd(G).
Given n > 1, the fan graph denoted by Fn, can be constructed by
joining n copies of the cycle graph C3 with a common vertex.
Theorem 2. For a fan graph Fn, with n > 1, we have χcd(Fn) = 3.
Proof. By the definition of fan graph, n copies of C3 is joined with a
common vertex, χ(Fn) > 3 and γ(Fn) = 1. Hence, χcd(Fn) > 3.
Let V (Fn) = {v1, v2, · · · , v2n+1} be the vertex set of Fn and let the
vertex at the center be labeled by v1. Let the vertex v1 be coloured by
colour 1 and the other two vertices of each copy of C3 are coloured by
colours 2 and 3. The vertex v1 dominates itself namely vertex coloured
1 and the vertices coloured 2 and 3. Hence, χcd(Fn) 6 3. Therefore,
χcd(Fn) = 3.
Y. Venkatakrishnan, V. Swaminathan 303
We recall from [1] that the double fan graph F2,n is isomorphic to
Pn + 2K1.
Theorem 3. For the double fan graph F2,n, with n > 2, we have
χcd(F2,n) = 3.
Proof. Let V1 = {v1, v2, · · · , vn} be the vertices of the path Pn and
V2 = {u1, u2} be the vertices of 2K1. Then V (F2,n) = V1 ∪ V2. The
vertices of V2 are adjacent to the vertices of V1. The set V2 forms a
minimum dominating set and γ(G) = 2. The vertices u1, v1, v3 forms a
cycle C3 and therefore χ(F2,n) > 3. Hence, χcd(F2,n) > 3.
The vertices u1 and u2 are non adjacent, they are coloured by colour 1.
Since, vi, 1 6 i 6 n is adjacent to both u1 and u2, these vertices are
alternatively coloured by colours 2 and 3. Any vertex vi in the path
dominates the vertices coloured 1 and the vertex u1 dominates the vertices
coloured 2 and 3. Hence, χcd(F2,n) 6 3. Therefore, χcd(F2,n) = 3.
The Helm graph Hn with n > 1, is defined to be the graph obtained
from a wheel graph W1,n by attaching a pendant edge at each vertex of
the n−cycle.
Theorem 4. For the Helm graph Hn, with n > 4, we have χcd(Hn) = n.
Proof. Let V (Hn) = {v1} ∪ V1 ∪ V2, where v1 is the central vertex,
V1 = {vi : 2 6 i 6 n + 1} be the vertices on the n−cycle and V2 = {vi :
n + 2 6 i 6 2n + 1} be the pendant vertices incident with n−cycle such
that vn+i is adjacent with vi, 2 6 i 6 n + 1.
The vertices v1 and vn+i, 2 6 i 6 2n+1 are non adjacent, these vertices
are coloured with colour 1. The remaining vertices vi, 2 6 i 6 n+1 on the
n−cycle can be coloured using a maximum of three colours. Therefore,
χ(Hn) 6 4 6 n. Since there are n pendant vertices, γ(Hn) > n. Hence,
χcd(Hn) > n.
Assume that the pendant vertices vn+i+1, 1 6 i 6 n be coloured with i.
The vertex v1 is coloured with colour n. Let v2 and v4 be coloured with
colour 2. The vertex adjacent to v2n+i, 3 6 i 6 n + 1; i 6= 4 namely vi is
coloured with colour i − 2. The partition
Π = {{vn+2, v3}, {vn+3, v2, v4}, {vn+4, v5}, · · · , {v2n, vn+1}, {v2n+1, v1}}
is a minimum colour class domination partition. The first two colour
classes are dominated by v2 and v3 and the last colour class is dominated
by the vertex vn. The colour classes {vn+i, vi+1}, 4 6 i 6 n is dominated
by the vertex vi. Hence, χcd(Hn) 6 n. Therefore, χcd(Hn) = n.
304 Colour class domination numbers
A flower graph Fln with n > 1, is defined to be the graph obtained
from a Helm graph Hn by joining each pendant vertex to the central
vertex of the Helm graph.
Theorem 5. For the flower graph Fln with n > 3, we have
χcd (Fln) =
{
3, if n is even
4, if n is odd
Proof. The central vertex is a dominating set. Therefore, γ(Fln) = 1.
Clearly, χ(Fln) = 3 if n is even or χ(FLn) = 4 if n is odd. Therefore,
χ(Fln) > 3 if n is even and χ(Fln) > 4 if n is odd.
Let v1 be the central vertex of W1,n. Let v2, v3, · · · , vn+1 be the vertices
in the n−cycle. The vertices vn+i is adjacent to vi, 2 6 i 6 n + 1 and v1.
Case(i): n is odd. The vertex v1 is coloured with colour 1. The
sequence of vertices vi, 2 6 i 6 n are coloured with colours 2 and 3
alternatively and vn+1 is coloured with colour 4. The remaining vertices
vi, n + 2 6 i 6 2n + 1 are coloured with colours 3 and 2 alternatively. The
vertex v1 dominates all the colour classes. Hence, χcd(Fln) 6 4. Therefore,
χ(Fln) = 4.
Case(ii): n is even. The vertex v1 is coloured with colour 1. The
sequence of vertices vi, 2 6 i 6 n + 1 are coloured with colours 2 and 3
alternatively. The remaining vertices vi, n + 2 6 i 6 2n + 1 are coloured
with colours 3 and 2 alternatively. The vertex v1 dominates all the colour
classes. Hence, χcd(Fln) 6 3. Therefore, χ(Fln) = 3.
The sun flower graph Sfn with n > 1, is defined to be the graph
obtained by adding n pendant edges to the central vertex of the flower
graph Fln.
Theorem 6. For the sun flower graph Sfn with n > 3, we have
χcd (Sfn) =
{
3, if n is even
4, if n is odd
Proof. The central vertex is a dominating set. Therefore, γ(Sfn) = 1.
Clearly, χ(Sfn) = 3 if n is even or χ(Sfn) = 4 if n is odd. Therefore,
χ(Sfn) > 3 if n is even and χ(Sfn) > 4 if n is odd.
Let V (Sfn) = {vi : 1 6 i 6 3n + 1}.
Y. Venkatakrishnan, V. Swaminathan 305
Case(i): n is odd. The vertex v1 is coloured with colour 1. The
sequence of vertices vi, 2 6 i 6 n are coloured with colours 2 and 3
alternatively and vn+1 is coloured with colour 4. The remaining vertices
vi, n + 2 6 i 6 2n + 1 are coloured with colours 3 and 2 alternatively
and the vertices vi, 2n + 2 6 i 6 3n + 1 are coloured with 2,3 or 4. The
vertex v1 dominates all the colour classes. Hence, χcd(Sfn) 6 4. Therefore,
χ(Sfn) = 4.
Case(ii): n is even. The vertex v1 is coloured with colour 1. The
sequence of vertices vi, 2 6 i 6 n + 1 are coloured with colours 2 and 3
alternatively. The remaining vertices vi, n + 2 6 i 6 2n + 1 are coloured
with colours 3 and 2 alternatively and the vertices 2n + 2 6 i 6 3n + 1 are
coloured with 2,3. The vertex v1 dominates all the colour classes. Hence,
χcd(Sfn) 6 3. Therefore, χ(Sfn) = 3.
References
[1] J.A. Gallian, A Dynamic Survey of Graph Labeling, Electronic Journal of Combi-
natorics 18(2011).
[2] K. Kavitha, N.G. David, Dominator coloring of some classes of graphs, Interna-
tional Journal of Mathematical Archive 3(11)(2012), 3954-3957.
[3] T. Haynes, S. Hedetniemi, and P. Slater, Fundamentals of Domination in Graphs,
Marcel Dekker, New York, 1998.
[4] T. Haynes, S. Hedetniemi, and P. Slater (eds.), Domination in Graphs: Advanced
Topics, Marcel Dekker, New York, 1998.
[5] Mustapha Chellali, F. Maffray, Dominator coloring in some classes of graphs,
Graphs and Combinatorics 28(2012), 97-107.
[6] V. Swaminathan, R. Sundareswaran, Color class domination in graphs, Mathe-
matical and Experimental Physics, Narosa Publishing house,2010.
[7] Y.B. Venkatakrishnan, V. Swaminathan, Color class domination number of middle
graph and center graph of K1,n, Cn, Pn, Advanced Modeling and Optimization
12(2)(2010), 233-237.
Contact information
Yanamandram B.
Venkatakrishnan
Department of Mathematics, SASTRA University
Tanjore, Tamilnadu, India
E-Mail(s): devasenavk@gmail.com
V. Swaminathan Ramanujan Research Center, S.N.College,
Madurai, India
E-Mail(s): swaminathan.sulanesri@gmail.com
Received by the editors: 01.02.2013
and in final form 01.03.2013.
|