δ-Dynamic chromatic number of Helm graph families

Abstract

An r-dynamic coloring of a graph G is a proper coloring c of the vertices such that $\left|c(N(v))\right|\ge min\left\{r,d(v)\right\}$, for each $v\in V(G)$, where N(v) and d(v) denote the neighborhood and the degree of v, respectively. The r-dynamic chromatic number of a graph G is the minimum k such that G has an r-dynamic coloring with k colors. In this paper, we obtain the $\mathit{\delta }$-dynamic chromatic number of middle, total, and central of helm graph, where $\mathit{\delta }=\underset{v\in V(G)}{min}\left\{d(v)\right\}$.

Keywords:

• r-dynamic coloring
• middle graph
• total graph
• central graph

AMS Subject Classifications:

• 05C15

Public Interest Statement

Graph coloring is one of the research areas that shaped the graph theory as we know it today; the attempts to prove many more theorems in graph colorings have inspired many notions that became important on their own. Also motivated the study of colorings of various families of graphs, including the graphs embedded in the surfaces of bounded genus. Even though a computer-assisted proof of the theorems was eventually found, many natural problems motivated by it remain unsolved and the study of colorings of planar graphs and of graphs on surfaces is one of the most active areas of research in modern graph theory.

This research paper outlines some of recently developed coloring, i.e. dynamic coloring. The new results in this paper are demonstrated by giving detailed proof based on our recent papers and to the best of our knowledge.

1. Introduction

Throughout this paper all graphs are finite and simple. The r-dynamic chromatic number was first introduced by Montgomery (2001). An r-dynamic coloring of a graph G is a map c from V(G) to a set of colors such that (i)if $uv\in E(G)$, then $c(u)\ne c(v)$, and (ii) for each vertex $v\in V(G),\left|c(N(v))\right|\ge min\left\{r,d(v)\right\}$, where N(v) denotes the set of vertices adjacent to v and d(v) is its degree. The r-dynamic chromatic number of a graph G, written ${\mathit{\chi }}_r(G)$, is the minimum k such that G has an r-dynamic proper k-coloring. The 1-dynamic chromatic number of a graph G is equal to its chromatic number. The 2-dynamic chromatic number of a graph has been studied under the name dynamic chromatic number in Ahadi, Akbari, Dehghana, and Ghanbari (2012), Akbari, Ghanbari, andJahanbakam (2009,2010), Alishahi (2012), Lai, Montgomery, and Poon (2003). There are many upper bounds and lower bounds for ${\mathit{\chi }}_d(G)$ in terms of graph parameters. For example,

for a graph G with $\mathrm{\Delta }(G)\ge 3$, Lai et al. (2003) proved that ${\mathit{\chi }}_d(G)\le \mathrm{\Delta }(G)+1$. An upper bound for the dynamic chromatic number of a d-regular graph G in terms of $\mathit{\chi }(G)$ and the independence number of G, $\mathit{\alpha }(G)$, was introduced in Dehghan and Ahadi (2012). In fact, it was proved that ${\mathit{\chi }}_d(G)\le \mathit{\chi }(G)+2{log}_2\mathit{\alpha }(G)+3$. Taherkhani gave in (2016) an upper bound for ${\mathit{\chi }}_2(G)$ in terms of the chromatic number, the maximum degree $\mathrm{\Delta }$ and the minimum degree $\mathit{\delta }$, i.e. ${\displaystyle {\mathit{\chi }}_2(G)-\mathit{\chi }(G)\le ⌈(\mathrm{\Delta }e)/\mathit{\delta }log\left(2e\left({\mathrm{\Delta }}^2+1\right)\right)⌉}$.

Li, Yao, Zhou, and Broersma proved in (2009) that the computational complexity of ${\mathit{\chi }}_d(G)$ for a 3-regular graph is an NP-complete problem. Furthermore, Liu and Zhou (2008) showed that to determine whether there exists a 3-dynamic coloring, for a claw free graph with maximum degree 3, is NP-complete.

In this paper, we study ${\mathit{\chi }}_r(G)$ when r is $\mathit{\delta }$, the minimum degree of the graph. We find the $\mathit{\delta }$-dynamic chromatic number for middle, total, and central graph of helm graph.

2. Results

Let G be a graph with vertex set V(G) and edge set E(G). The middle graph (Michalak, 1981) of G, denoted by M(G) is defined as follows. The vertex set of M(G) is $V(G)\cup E(G)$. Two vertices x, y of M(G) are adjacent in M(G) in case one of the following holds: (i) x, y are in E(G) and x, y are adjacent in G. (ii) x is in V(G), y is in E(G), and x, y are incident in G.

Let G be a graph with vertex set V(G) and edge set E(G). The total graph (Michalak, 1981) of G,  denoted by T(G) is defined in the following way. The vertex set of T(G) is $V(G)\cup E(G)$. Two vertices x, y of T(G) are adjacent in T(G) in case one of the following holds: (i) x, y are in V(G) and x is adjacent to y in G. (ii) x, y are in E(G) and x, y are adjacent in G. (iii) x is in V(G), y is in E(G) and x, y are incident in G.

The central graph (Vernold Vivin, 2007) C(G) of a graph G is obtained from G by subdividing each edge of G exactly once and then joining each pair of vertices of the original graph which were previously non-adjacent.

The helm graph $H_n$ is the graph obtained from an n-wheel graph by adjoining a pendent edge at each node of the cycle. Where $V(H_n)=\{v\}\cup \{v_1,v_2,\dots ,v_{n-1}\}\cup \{u_1,u_2,\dots ,u_{n-1}\}$ and $E(H_n)=\{e_i:1\le i\le n-1\}\cup \{e_i^{\prime }:1\le i\le n-1\}\cup \{s_i:1\le i\le n-1\},$ where $e_i$ is the edge $v{v}_i$$(1\le i\le n-1)$, $e_i^{\prime }$ is the edge $v_i{v}_{i+1}$$(1\le i\le n-2)$ and $s_i$ is the edge $v_i{u}_i$$(1\le i\le n-1)$. This notation is valid through the entire paper.

Theorem 2.1

Let $n\ge 8.$ The $\mathit{\delta }$-dynamic chromatic number of the middle graph of a helm of order $2n-1$ is ${\displaystyle {\mathit{\chi }}_{\mathit{\delta }}(M(H_n))=n}$.

Proof

By the definition of middle graph, $V(M(H_n))$$=V(H_n)\cup E(H_n)=\{v\}\cup \{v_i:1\le i\le n-1\}\cup \{u_i:1\le i\le n-1\}\cup \{e_i:1\le i\le n-1\}\cup \{e_i^{\prime }:1\le i\le n-1\}\cup \{s_i:1\le i\le n-1\}$. The vertices v and $\{e_i:1\le i\le n-1\}$ induce a clique of order $K_n$ in $M(H_n)$. Thus, ${\mathit{\chi }}_{\mathit{\delta }}(M(H_n))\ge n.$

Consider the following n-coloring of $M\left(H_n\right)$:

For $1\le i\le n-1$, assign the color $c_i$ to $e_i$ and assign the color $c_n$ to v. For $1\le i\le n-1$, assign the color $c_n$ to $u_i$, $deg(u_i)=\mathit{\delta }(M(H_n))=1$. For $1\le i\le n-1$, assign to $e_i^{\prime }$ one of the allowed colors—such color exists, because $deg(u_i)=8$. For $1\le i\le n-1$, if any, assign to vertex $v_i$ one of the allowed colors—such color exists, because $deg(v_i)=4$. For $1\le i\le n-1$, if any, assign to vertex $s_i$ one of the allowed colors—such color exists, because $deg(s_i)=3$. An easy check shows that N(v) contains an induced clique of order 5, for every $v\in V\left(M\left(H_n\right)\right)$. Thus, this coloring is a $\mathit{\delta }$-dynamic coloring. Hence, ${\mathit{\chi }}_{\mathit{\delta }}(M(H_n))\le n.$ Therefore, ${\mathit{\chi }}_{\mathit{\delta }}(M(H_n))=n$, $\forall n\ge 8$. $\square$

Theorem 2.2

Let $n\ge 9$. The $\mathit{\delta }$-dynamic chromatic number of the total graph of a helm of order $2n-1$ is ${\displaystyle {\mathit{\chi }}_{\mathit{\delta }}(T(H_n))=n}$.

Proof

By the definition of total graph $V(T(H_n))$$=V(H_n)\cup E(H_n)=\{v\}\cup \{v_i:1\le i\le n-1\}\cup \{u_i:1\le i\le n-1\}\cup \{e_i:1\le i\le n-1\}\cup \{e_i^{\prime }:1\le i\le n-1\}\cup \{s_i:1\le i\le n-1\}$. The vertices v and $\{e_i:1\le i\le n-1\}$ induce a clique of order $K_n$ in $T(H_n)$. Thus, ${\mathit{\chi }}_{\mathit{\delta }}(T(H_n))\ge n.$

Consider the following n-coloring of $T\left(H_n\right)$:

For $1\le i\le n-1$, assign the color $c_i$ to $e_i$ and assign the color $c_n$ to v. For $1\le i\le n-1$, assign to $u_i$ one of the allowed colors—such color exists, because $\mathit{\delta }(u_i)=deg(u_i)=2$. For $1\le i\le n-1$, assign to $e_i^{\prime }$ one of the allowed colors—such color exists, because $deg(u_i)=8$. For $1\le i\le n-1$, if any, assign to vertex $v_i$ one of the allowed colors—such color exists, because $deg(v_i)=8$. For $1\le i\le n-1$, if any, assign to vertex $s_i$ one of the allowed colors—such color exists, because $deg(s_i)=5$. An easy check shows that N(v) contains an induced clique of order 5, for every $v\in V\left(M\left(H_n\right)\right)$. Thus, this coloring is a $\mathit{\delta }$-dynamic coloring. Hence, ${\mathit{\chi }}_{\mathit{\delta }}(T(H_n))\le n.$ Therefore, ${\mathit{\chi }}_{\mathit{\delta }}(T(H_n))=n$, $\forall n\ge 9$. $\square$

Theorem 2.3

Let $n\ge 4.$ The $\mathit{\delta }$-dynamic chromatic number of the central graph of a helm of order $2n-1$ is ${\displaystyle {\mathit{\chi }}_{\mathit{\delta }}(C(H_n))=2n-1}$.

Proof

By the definition of central graph, subdividing each edge of $H_n$ exactly once and then joining each pair of vertices of $H_n$ which were non-adjacent. Let $V(C(H_n))$$=V(H_n)\cup E(H_n)=\{v\}\cup \{v_i:1\le i\le n-1\}$$\cup \{u_i:1\le i\le n-1\}\cup \{e_i:1\le i\le n-1\}\cup \{e_i^{\prime }:1\le i\le n-1\}\cup \{s_i:1\le i\le n-1\}$. Clearly, the graph induced by $\{v_{2i}:i=1,2,\dots ,\lfloor (n-1)/2\rfloor \}$ is a complete graph. Thus, a proper coloring assigns at least $\lfloor (n-1)/2\rfloor$ colors to them. The same happens with the subgraph induced by $\{v_{2i-1}:i=1,2,\dots ,\lfloor (n-1)/2\rfloor \}$. Moreover, if we are considering a $\mathit{\delta }$-dynamic coloring when $n-1$ is odd $v_{n-1}$ should have a different color from $v_{2i-1}$, $i=1,2,\dots ,(n-1)/2$, because $v_{n-1}$ and $v_1$ are the only neighbors of $e_{n-1}^{\prime }$, and $v_{n-1}$ is adjacent to $v_{2i-1}$, $i=2,\dots ,(n-1)/2$. A similar reasoning also shows that in a $\mathit{\delta }$-dynamic coloring, the colors assigned to odd vertices should be different to the colors assigned to even vertices and that all of them should be different from the color assigned to v.

It is also shown that in a $\mathit{\delta }$-dynamic coloring, the colors assigned to vertices $\{v\}\cup \{v_i:1\le i\le n-1\}$ should be different to the colors assigned to the vertices of $\{u_i:1\le i\le n-1\}$. Since, the vertices $\{u_i:1\le i\le n-1\}$ and v induces a clique of order $K_n$ in $C(H_n)$ and the vertices $\{v_i:1\le i\le n-1\}$ adjacent to $\{u_j:1\le j\le n-1\}\forall i\ne j.$ But, any three consecutive vertices of the path must be colored differently in any dynamic coloring. Since, the first and third vertices are the only neighbors of the second vertex and must be colored differently (by the condition of dynamic coloring) and also differently from the second vertex. So, the same color to $\{v_i:1\le i\le n-1\}$ and $\{u_j:1\le j\le n-1\}\forall i=j$ is impossible. Thus, ${\displaystyle {\mathit{\chi }}_{\mathit{\delta }}(C(H_n))\ge 2n-1}$.

Consider the following $2n-1$-coloring of $C\left(H_n\right)$:

For $1\le i\le n-1$, assign the color $c_i$ to $v_i$ and assign the color $c_n$ to v. For $1\le i\le n-1$, assign the color $c_{n+i}$ to $u_i$. For $1\le i\le n-1$, assign to vertices $s_i$, $e_i^{\prime }$ and $e_i$ one of the allowed colors—such color exists, because $deg(s_i)=deg(e_i^{\prime })=deg(e_i)=\mathit{\delta }(C(H_n))=2$. An easy check shows that this coloring is a $\mathit{\delta }$-dynamic coloring. Hence, ${\mathit{\chi }}_{\mathit{\delta }}(C(H_n))\le 2n-1$. Therefore, ${\mathit{\chi }}_{\mathit{\delta }}(C(H_n))=2n-1$. $\square$

Acknowledgements

With due Respect, the authors sincerely thank the referee for his careful reading, excellent comments and fruitful suggestions that have resulted in the improvement of the quality of this manuscript.

Additional information

Funding

The authors received no direct funding for this research.

Notes on contributors

N. Mohanapriya

N. Mohanapriya is working as an assistant professor in the Department of Mathematics, RVS Technical Campus—Coimbatore, Tamil Nadu, India. She is pursuing her Part-time (Category B) PhD in Bharathiar University, Coimbatore in the field of graph theory, particularly in graph colorings. She has published five research papers in International and National Journals and Conferences.

J. Vernold Vivin

M. Venkatachalam is working as an assistant professor in the Department of Mathematics, RVS Technical Campus—Coimbatore, Tamil Nadu, India. His research areas of interests are graph theory and inventory models. He has published more than 20 research papers in International and National Journals and Conferences.

M. Venkatachalam

M. Venkatachalam is working as an assistant professor in the Department of Mathematics, RVS Technical Campus—Coimbatore, Tamil Nadu, India. His research areas of interests are graph theory and inventory models. He has published more than 20 research papers in International and National Journals and Conferences.