On dynamic colouring of cartesian product of complete graph with some graphs

ABSTRACT

A proper vertex colouring is called a 2-dynamic colouring, if for every vertex v with degree at least 2, the neighbours of v receive at least two colours. The smallest integer k such that G has a dynamic colouring with k colours denoted by ${\chi }_2\left(G\right)$. We denote the cartesian product of G and H by $G◻H$. In this paper, we find the 2-dynamic chromatic number of cartesian product of complete graph with complete graph $K_r◻K_s$, complete graph with complete bipartite graph $K_n◻K_{1,s}$ and wheel graph with complete graph $W_l◻K_n$.

Keywords:

• Dynamic colouring
• cartesian product
• join and wheel

2000 Mathematics Subject Classification:

• 05C15

1. Introduction

Graphs in this note are simple and finite [1,2]. We denote the edge set and vertex set of G, by $E\left(G\right)$ and $V\left(G\right)$, respectively. The number of vertices of G is called order of G. The degree of a vertex $v_i$, in a graph G denoted by $d_i$ or $d\left(v_i\right)$, is the minimum number of edges incident in it, where $\delta \left(G\right)$ and $\mathrm{\Delta }\left(G\right)$ denotes minimum and maximum vertex degree in a graph G. A proper vertex colouring of G is a function $c:V\left(G\right)\to L$, with property: if $u,v\in V\left(G\right)$ are adjacent, then $c\left(u\right)$ and $c\left(v\right)$ are different. A vertex k-colouring is a proper vertex colouring with $|L|=k$. The smallest integer k such that G has a vertex k-colouring is called the chromatic number of G and denoted by $\chi \left(G\right)$. A proper vertex k-colouring is called dynamic [3,4] if for every vertex v with degree at least 2, the neighbours of v receive atleast two different colours. The smallest integer k such that G has a dynamic k-colouring is called 2-dynamic chromatic number of G and denoted by ${\chi }_2\left(G\right)$. Moreover, 2-dynamic colouring is generally said to be dynamic colouring.

Generally, a proper vertex k-colouring is called r-dynamic [5] if for every vertex v with degree at least r, the neighbors of v receive atleast r different colours. The smallest integer k such that G has a dynamic k-colouring is called r-dynamic chromatic number of G and denoted by ${\chi }_r\left(G\right)$.

For any $v\in V\left(G\right),N_G\left(V\right)$ denotes the neighbour set of v in G. Let c be a proper vertex colouring of G. For any $v\in V\left(G\right)$, we mean $c\left(N_G\right(V\left)\right)$ the set of colours appearing in the neighbors of v in G.

Let G and H be two graphs. We call that the cartesian product of G and H, $G◻H$, is a graph with the vertex set $V\left(G\right)\times V\left(H\right)$ such that two vertices $(u,v)$ and $(x,y)$ are adjacent if and only if u = x and $vy\in E\left(H\right)$ or v = y and $ux\in E\left(G\right)$. Clearly $\mathrm{△}\left(G◻H\right)=\mathrm{△}\left(G\right)+\mathrm{△}\left(H\right)$.

Similarly, join of G and H, G + H, is a graph with the vertex set $V\left(G\right)\cup V\left(H\right)$ and edge set $E\left(G\right)\cup E\left(H\right)\cup \{uv:u\in E(G)\mathrm{a}\mathrm{n}\mathrm{d}v\in E(H\left)\right\}$.

A graph is said to be wheel on n-vertices, it is a join of cycle of length n−1 and $K_1$. Moreover, the minimum number of vertices in any wheel is 4.

2. Preliminaries

We shall make use of the following lemmas, in order to prove our results,

Lemma 2.1

[6]

For any positive integer n, ${\chi }_2\left(C_n\right)=\left\{\begin{array}{ll}3& \mathrm{i}\mathrm{f}n|3\\ 5& \mathrm{i}\mathrm{f}n=5\\ 4& \mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e}.\end{array}\right.$

Lemma 2.2

[7]

For i and $j\ge 2,$ ${\chi }_2\left(K_{i,j}\right)=4$ and ${\chi }_2\left(K_{1,j}\right)=3$.

Lemma 2.3

[7]

For any positive integer n, ${\chi }_2\left(K_n\right)=n$.

Lemma 2.4

[8]

Let G and H be two graphs. If $\delta \left(G\right)\ge 2,$ ${\chi }_2\left(G◻H\right)\le max\left({\chi }_2\left(G\right),\chi \left(H\right)\right).$

Lemma 2.5

[9]

Let G be a connected graph then, ${\chi }_r\left(G\right)\ge {\chi }_{r-1}\left(G\right)\ge \cdots \ge {\chi }_2\left(G\right)\ge \chi \left(G\right).$

Lemma 2.6

[2]

For any positive integer n, $\chi \left(C_n\right)=\left\{\begin{array}{ll}2& \mathrm{i}\mathrm{f}n\mathrm{i}\mathrm{s}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n}\\ 3& \mathrm{i}\mathrm{f}n\mathrm{i}\mathrm{s}\mathrm{o}\mathrm{d}\mathrm{d}.\end{array}\right.$

3. Sub results

For finding the dynamic chromatic number of wheel, we need the dynamic chromatic number of join of two graphs.

Theorem 3.1

For any two connected graphs G and H, then ${\chi }_2\left(G+H\right)=\chi \left(G\right)+\chi \left(H\right).$

Proof.

Let $V\left(G\right)=\{u_i:1\le i\le r\}$ and $V\left(H\right)=\{v_j:1\le j\le s\}$. By the definition of join of two graphs, $\begin{array}{rl}V\left(G+H\right)& =V\left(G\right)\cup V\left(H\right)\mathrm{a}\mathrm{n}\mathrm{d}\\ E\left(G+H\right)& =E\left(G\right)\cup E\left(H\right)\cup \{u_i{v}_j:u_i\in E\left(G\right)\mathrm{a}\mathrm{n}\mathrm{d}\\ v_j& \in E\left(H\right)\}.\end{array}$ Consider the vertex colourings $c_1:V\left(G\right)\to \left\{1,2,\dots ,\chi \left(G\right)\right\}$ and $c_2:V\left(H\right)\to \left\{1,2,\dots ,\chi \left(H\right)\right\}.$ Let $k=\chi \left(G\right)+\chi \left(H\right)$ and define $c:V(G+H)\to \{1,2,\dots ,k\}$. For every $u_i\in V\left(G\right)$, provide $c\left(u_i\right)=c_1\left(u_i\right)$ and for every $v_j\in V\left(H\right)$, $c\left(v_j\right)=c_2\left(v_j\right)+max\left\{c_1\left(u_i\right):i=1,2,\dots r\right\}.$ Now, we claim that c is a dynamic colouring of G + H. Clearly, c is a proper colouring. Moreover, for vertices $w\in V(G+H)$ having $d\left(w\right)\ge 2$, $|c\left(N_{G+H}\left(w\right)\right)|\ge 2,$ even still $G=K_2$ and $H=K_1$ and it completes the proof.

Corollary 3.2

For any positive integer n, ${\chi }_2\left(W_n\right)=\left\{\begin{array}{ll}3& \mathrm{i}\mathrm{f}n\mathrm{i}\mathrm{s}\mathrm{o}\mathrm{d}\mathrm{d}\\ 4& \mathrm{i}\mathrm{f}n\mathrm{i}\mathrm{s}\mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n}\end{array}\right.$

Proof.

From the definition of wheel $W_n=C_{n-1}+K_1$. Using Theorem 3.1, ${\chi }_2\left(W_n\right)=\chi \left(C_{n-1}\right)+\chi \left(K_1\right)=\chi \left(C_{n-1}\right)+1$ and it completes the proof.

4. Main results

In the next theorem, we obtain the dynamic chromatic number of cartesian product between two complete graphs.

Theorem 4.1

For any two positive integers $r,s,$ then ${\chi }_2\left(K_r◻K_s\right)=\left\{\begin{array}{ll}4& \mathrm{i}\mathrm{f}r=s=2\\ max\left(r,s\right)& \mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e}.\end{array}\right.$

Proof.

Let $V\left(K_r\right)=\{u_i:0\le i\le r-1\}$ and $V\left(K_s\right)=\{v_j:1\le j\le s\}$. By the definition of cartesian product, $V\left(K_r◻K_s\right)=\bigcup _{i=0}^{r-1}\{u_i{v}_j:1\le j\le s\}$. For proving this theorem we need to consider two cases,

Case 1: When r = s = 2.

Clearly, $K_2◻K_2=C_4$. So, ${\chi }_2\left(K_2◻K_2\right)={\chi }_2\left(C_4\right)=4=r+s$.

Case 2: When both $r,s\ne 2$.

Consider the mapping $f\ni f:V\left(K_r◻K_s\right)\to \{1,2,\dots ,k\},\mathrm{w}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{e}k=max\left(r,s\right).$ Define, $f\left(u_i{v}_j\right)=\left\{\begin{array}{ll}k& \mathrm{i}\mathrm{f}i+j\equiv \left(0modk\right)\\ i+jmodk& \mathrm{i}\mathrm{f}i+j\not\equiv \left(0modk\right)\end{array}\right.$ since $f\left(u_i{v}_j\right)\ne f\left(u_i{v}_{j+1}\right)$ and $f\left(u_i{v}_j\right)\ne f\left(u_{i+1}{v}_j\right)\mathrm{\forall }i\in \{0,1,\dots ,r-1\},j\in \{1,2,\dots ,s\}.$ so, f produces a proper colouring for $K_r◻K_s$. Next we need to show f is dynamic colouring. Since for every vertex $(u_i,v_j)\in V\left(K_r◻K_s\right)$, $|f\left(N_{K_r◻K_s}\left(u_i,v_j\right)\right)|=\mathrm{△}\left(G\right)+\mathrm{△}\left(H\right)\ge 2$ even r or s is 1 and the proof is complete.

Generally, consider the p-dynamic colouring, ${\chi }_p\left(K_r◻K_s\right)={\chi }_2\left(K_r◻K_s\right)=\chi \left(K_r◻K_s\right),$ whenever $p\in \{3,4,\dots ,max(r,s)-1\}$, but it varies when $p\ge max(r,s)$. This will not suit for $K_2◻K_2$, since ${\chi }_{\delta }\left(G\right)={\chi }_{\delta -1}\left(G\right)=\cdots ={\chi }_2\left(G\right)>\chi \left(G\right)=2,$ where $\delta =2$ in $K_2◻K_2$.

Corollary 4.2

For positive integers $r_i\ge 2$ and ∃ atleast one $r_i\ge 4,$ then ${\chi }_2\left(K_{r_1}◻K_{r_2}◻\cdots ◻K_{r_i}\right)=max\left\{r_j:1\le j\le i\right\}$ where $i\in \{2,3,4\dots \}$.

Corollary 4.3

${\chi }_2(K_2◻K_2◻\cdots ◻K_2)=4,$ where we can take cartesian product in any number of times.

In the next two theorem, we obtain the dynamic chromatic number of cartesian product between complete graph and complete bipartite graphs.

Theorem 4.4

For any two positive integers $s\ge 2$ and n, then ${\chi }_2\left(K_n◻K_{1,s}\right)=\left\{\begin{array}{ll}3& \mathrm{i}\mathrm{f}n=1\\ 4& \mathrm{i}\mathrm{f}n=2\\ n& \mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e}.\end{array}\right.$

Proof.

Let $V\left(K_n\right)=\left\{u_i:1\le i\le n\right\}$ and $V\left(K_{1,s}\right)=\left\{w\right\}\cup \left\{v_j:1\le j\le s\right\}.$ By the definition of cartesian product, $V\left(K_n◻K_{1,s}\right)=\bigcup _{i=1}^n\left\{u_i{v}_j:1\le j\le s\right\}\cup \bigcup _{i=1}^n\left\{u_{i}w\right\}.$ Consider a mapping $f\ni f:V\left(K_r◻K_{1,s}\right)\to \{1,2,\dots ,k\}$. For proving this theorem we need to consider three cases,

Case 1: When n = 1

Clearly, $K_1◻K_{1,s}=K_{1,s}$. So ${\chi }_2\left(K_1◻K_{1,s}\right)={\chi }_2\left(K_{1,s}\right)=3$ where $k=3$ in this case.

Case 2: When n = 2$K_2◻K_{1,s}$contains a subgraph of $K_2◻K_2$. So, ${\chi }_2\left(K_2◻K_{1,s}\right)\ge {\chi }_2\left(K_2◻K_2\right)=4.$ To prove the reverse inequality, let us define a map f in such a way that $f\left(u_i{v}_j\right)=i$ and $f\left(u_{i}w\right)=i+2\mathrm{\forall }i\in \{1,2\}$. Clearly f preserves dynamic colouring and using this $K_2◻K_{1,s}$ requires atmost 4 colours. It clearly says ${\chi }_2\left(K_2◻K_{1,s}\right)=4$.

Case 3: When $n\ge 3$

Using Lemma 2.4, $\begin{array}{rl}{\chi }_2\left(K_n◻K_{1,s}\right)& \le max\left({\chi }_2\left(K_n\right),\chi \left(K_{1,s}\right)\right)\\ & =max\left(n,2\right)=n.\end{array}$ For, the reverse inequality, $K_n◻K_{1,s}$ contains $K_n$. so, it requires atleast n colours for dynamic colouring and this proves the theorem.

From the Theorem 4.4, when r = 1 then $K_2◻K_{1,1}=K_2◻K_2=C_4.$ Using Theorem 4.1, ${\chi }_2\left(K_2◻K_{1,1}\right)={\chi }_2\left(K_2◻K_2\right)=4$.

Theorem 4.5

For any positive integers $r,s\ge 2$ and n, then ${\chi }_2\left(K_n◻K_{r,s}\right)=\left\{\begin{array}{ll}4& \mathrm{i}\mathrm{f}n=1,2\\ n& \mathrm{i}\mathrm{f}n\ge 3.\end{array}\right.$

Proof.

Let $V\left(K_n\right)=\left\{u_i:1\le i\le n\right\}$ and $V\left(K_{r,s}\right)=\left\{w_j:1\le j\le r\right\}\cup \left\{v_l:1\le l\le s\right\}.$ By the definition of cartesian product, $\begin{array}{rl}& V\left(K_n◻K_{1,s}\right)\\ & =\bigcup _{i=1}^n\left\{u_i{v}_l:1\le l\le s\right\}\cup \bigcup _{i=1}^n\left\{u_i{w}_j:1\le j\le r\right\}.\end{array}$ Consider a mapping $f\ni f:V\left(K_n◻K_{r,s}\right)\to \left\{1,2,\dots ,k\right\}.$ We prove the theorem on the number of vertices in complete graph,

Case 1: When n = 1.

Clearly, $K_1◻K_{r,s}=K_{r,s}$. So, ${\chi }_2\left(K_1◻K_{r,s}\right)={\chi }_2\left(K_{r,s}\right)=4$, where k = 4 in this case.

Case 2: When n = 2

$K_2◻K_{2,s}$contains a subgraph of $K_2◻K_2$. So, ${\chi }_2\left(K_2◻K_{4,s}\right)\ge {\chi }_2\left(K_2◻K_2\right)=4.$ To prove the reverse inequality, by Lemma 2.4, $\begin{array}{rl}{\chi }_2\left(K_{r,s}◻K_2\right)& \le max\left({\chi }_2\left(K_{r,s}\right),\right.\\ \left.\chi \left(K_2\right)\right)& =max\left(4,2\right)=4.\end{array}$ It clearly says, ${\chi }_2\left(K_n◻K_{r,s}\right)=4$, where k = 4 in this case.

Case 3: When $n\ge 3$

Define the mapping f by $f\left(u_i{w}_j\right)=i$ and $f\left(u_i{v}_l\right)=\left\{\begin{array}{ll}n& \mathrm{i}\mathrm{f}i+1\equiv 0\left(modn\right)\\ i+1\left(modn\right)& \mathrm{i}\mathrm{f}i+1\not\equiv 0\left(modn\right)\end{array}\right.$ For every $i=1,2,\dots ,n$. so, f produces a proper colouring for $K_n◻K_{r,s}$ with $n(=k)$ colours. Next we need to show f is dynamic colouring. Since for every vertex $\left(u,w\right)\in V\left(K_n◻K_{r,s}\right),\left|f\left(N_{K_n◻K_{r,s}}\left(u,w\right)\right)\right|=n-1\ge 2$ where n is minimum 3 in this case. Thus f contributes dynamic colouring and the proof is complete.

In the next theorem, we obtain the dynamic chromatic number of cartesian product of wheel graph with complete graph.

Theorem 4.6

For any positive integer $l\ge 4$ and n, then ${\chi }_2\left(W_l◻K_n\right)=max\{{\chi }_2\left(W_l\right),{\chi }_2\left(K_n\right)\}.$

Proof.

Let $V\left(W_l\right)=\{u_i:0\le i\le l-1\}$ and $V\left(K_n\right)=\{v_j:0\le j\le n-1\},$ where $u_0$ is the centre vertex in the wheel $W_l$ i.e. $u_0$ is adjacent to remaining l−1 vertices. By the definition of cartesian product, $V\left(W_l◻K_n\right)=\bigcup _{i=0}^{l-1}\left\{u_i{v}_j:0\le j\le n-1\right\}.$ Consider a mapping $f\ni f:V\left(K_r◻K_{1,s}\right)\to \left\{1,2,\dots ,k\right\},$ where $k=max\left\{{\chi }_2\right(W_l),{\chi }_2(K_n\left)\right\}$.

For proving the theorem, we need to consider two cases,

Case 1: When l−1 is even.

Define, $f\left(u_i{v}_j\right)=\left\{\begin{array}{ll}j\left(modk\right)& \mathrm{i}\mathrm{f}i=0\\ j+1\left(modk\right)& \mathrm{i}\mathrm{f}i=1,3,\dots ,l-2\\ j+2\left(modk\right)& \mathrm{i}\mathrm{f}i=2,4,\dots ,l-1\end{array}\right.$

Case 2: When l−1 is odd.

Define, $f\left(u_i{v}_j\right)=\left\{\begin{array}{ll}j\left(modk\right)& \mathrm{i}\mathrm{f}i=0\\ j+1\left(modk\right)& \mathrm{i}\mathrm{f}i=1,3,\dots ,l-3\\ j+2\left(modk\right)& \mathrm{i}\mathrm{f}i=2,4,\dots ,l-2\\ j+3\left(modk\right)& \mathrm{i}\mathrm{f}i=l-1\end{array}\right.$ For the above two cases, we claim that f is a dynamic colouring of $W_l◻K_n$. Clearly, f is a proper colouring. Moreover, for every vertex $u_i\in V\left(W_l\right),|c\left(N_{W_l}\left(u_i\right)\right)|\ge 2,$ where c is dynamic colouring for $W_l$. Since for every vertex $(u_i,v_j)\in V\left(W_l◻K_n\right)$, $|f\left(N_{W_l◻K_n}\right(u_i,v_j\left)\right)|\ge 2$ and the proof is complete.

Disclosure statement

No potential conflict of interest was reported by the authors.