Center Coloring in Graph Operations

Zeynep Ors Yorgancioglu¹, Pinar Dündar²

¹Scholl of Maritime and Port Management Program, Yasar University, Izmir, Turkey.
²Faculty of Mathematics, Ege University, Izmir, Turkey.

DOI: 10.4236/oalib.1107318                

Abstract

Center coloring Cc(G) is a kind of coloring that is to color the vertices of a graph G is such a way that if vertices have different distances from the center then they must receive different colors. Two adjacent vertices can receive the same color. In this paper we observed the behavior of the center coloring under several graph operations such as adding, removing, union, join, sequential join, Cartesian product, corona product of graphs and we get some bounds for center coloring number in these graph operations.

Keywords

Graph, Graph Coloring, Graph Operations

1. Introduction

Graph coloring is one of the most important, well-known and studied subfields of graph theory. Center coloring [1] is the one of the graph coloring techniques. This coloring can be used to solve several problems like hierarchy problems, earthquake motion problems, etc. In this paper we observed center coloring in graph operations.

Adding a vertex v to a connected G graph is connecting v to all the vertices of the graph [2].

Removing a vertex v from the connected G graph, is deleting v and all the edges connected to v vertex [2].

Adding an edge e to a connected G graph is connecting e with the vertex to be added [3].

Removing an edge e from the connected G graph, is deleting e and edge set $E\left(G\right)-\left\{e\right\}$ [3].

The Union $G=G_1\cup G_2$ has $V\left(G\right)=V\left(G_1\right)\cup V\left(G_2\right)$ and $E\left(G\right)=E\left(G_1\right)\cup E\left(G_2\right)$ [2].

The Join $G_1+G_2$ of graphs $G_1$ and $G_2$ is a graph with vertex set $V\left(G_1\right)\cup V\left(G_2\right)$ and edge set $E\left(G_1\right)\cup E\left(G_2\right)\cup \left\{uv:u\in V\left(G_1\right)\text{and}v\in V\left(G_2\right)\right\}$ [2].

The Sequential Join $G_1+G_2+\cdots +G_n$ of graphs $G_1,G_2,\cdots ,G_n$ is a graph of three or more disjoint graphs [2],

$\left(G_1+G_2\right)\cup \left(G_2+G_3\right)\cup \cdots \cup \left(G_{n-1}+G_n\right)$.

Thorny graph $G^{*}$ is any graph that can be obtained from a parent connected graph G by attaching $p_i\ge 0$ new vertices of degree one to each vertex i, is called thorny graph [4].

The Cartesian Product G × H of graphs G and H has the vertex set $V\left(G\times H\right)=V\left(G\right)\times V\left(H\right)$ and (a, x) (b, y) is an edge of G × H if a = b and $xy\in E\left(H\right)$, or $ab\in E\left(H\right)$ and x = y [2].

The Corona Product G o H is defined as the graph obtained from G and H by taking one copy of G and V(G) copies of H and then joining by an edge each vertex of the ith copy of H is named (H, i) with the ith vertex of G [2].

Some graphs G have the property that each vertex of G is a central vertex. A graph is self-centered if every vertex is in the center.

Theorem 1.1: If the graph G is a self-centered graph then $C_c=1$ [1].

While finding center coloring number of any graph, if the center of a graph consists more than one vertex, these vertices are contracted. So after the vertices are contracted, the center of a graph consists a single vertex.

Several results on center coloring number are surveyed and compared with the graph operations.

We refer to the book [5] for graph theory notation and terminology.

2. Center Coloring Number of Graph Operations

In this part of the study, the number of center coloring in new graphs formed as a result of applying various graph operations to one graph or more than one graph was examined.

Theorem 2.1: Let G is a connected graph, if we delete a vertex v that is not a center from a graph G, then we obtain,

$1\le C_c\left(G-v\right)\le C_c\left(G\right)$.

Proof: The communication from center to other vertices is continued because v is not a center. Just no communication with deleted vertex. When v is deleted from the graph, G can be a self-centered graph and its center coloring number is 1 from theorem 1.1.

Theorem 2.2: Let G is a connected graph, if we add a vertex v to any vertex of a graph, then we obtain,

$1\le C_c\left(G+v\right)\le 2$.

Proof: When v is added to the graph G shown in Figure 1, v is the center and the distance from vertex v to the other vertices is 1. And one more color for vertex v so its center coloring number is 2. G can be self-centered graph if v is added to G and its center coloring number is 1 from theorem 1.1.

Figure 1. Center coloring of the graph G + v.

Theorem 2.3: Let G is a connected graph, if the deleted edge is not a bridge, we obtain,

$\left|C_c\left(G\right)-C_c\left(G-e\right)\right|\le 1$.

Proof: If the deleted edge is e is one of the edges connecting the central vertices then the number of center coloring may increase by 1 if not there will be no change in the center coloring number.

Theorem 2.4: Let $G_1$ and $G_2$ are connected graphs, $G=G_1\circ G_2$ is a corona operation then we obtain,

$1\le C_C\left(G\right)\le 2+C_C\left(G_1\right)$.

Proof: Theorem 1.1 verifies the lower bound. To verify the upper bound, in corona operation the copy of $G_2$ is connected with every vertex of $G_1$ by edges as shown in Figure 2. So from theorem 2.2 $C_C\left(G_2\right)\le 2$. The center of $G_1$ is also a center of G so the center coloring number $G_1$ is not changed.

Figure 2. Center coloring of $G=G_1\circ G_2$.

Theorem 2.5: Let $G^{\ast }$ is a thorny of G then we obtain $C_c\left(P_5\right)<C_c\left(P_5{}^{\ast }\right)$.

Proof: In thorny operation the central vertex is not changed as shown in Figure 4. But as the number of vertex will increase, the distance from the center to the vertices is at least as the graph G. If $rad\left(G\right)<rad\left(G^{\ast }\right)$ then $C_c\left(G\right)<C_c\left(G^{\ast }\right)$. If $rad\left(G\right)=rad\left(G^{\ast }\right)$ then $C_c\left(G\right)=C_c\left(G^{\ast }\right)$. So center coloring number of $G^{\ast }$ is at least $C_c\left(G\right)$. If we compare the center coloring number of path in Figure 3 and thorny path in Figure 4, it is obvious that $C_c\left(P_5\right)<C_c\left(P_5{}^{\ast }\right)$.

Figure 3. $C_c\left(P_5^{}\right)=3$.

Figure 4. $C_c\left(P_5^{\ast }\right)=4$.

Theorem 2.6: Let $K_n$ and $K_m$ are complete graphs. Using the join operation we obtain,

$C_c\left(K_n+K_m\right)<C_c\left(K_n\right)+C_c\left(K_m\right)$.

Proof: A complete graph is a self-centered graph so from theorem 1.1 its center coloring number is one. Because the join of two complete graphs are another complete graph, the center coloring number is one.

Theorem 2.7: Let $G_n$ and $G_m$ are connected graphs. Using the join operation we obtain

$C_c\left(G_n+G_m\right)\le C_c\left(G_n\right)+C_c\left(G_m\right)$.

Proof: The distance from the center to the vertices is reduced or maintained therefore the distance is reduced between every vertices of $G_n$ is connected with every vertex of $G_m$ in the join of graph $G_n$ and $G_m$.

Theorem 2.8: For $G_1+G_2+\cdots +G_n$ graphs with sequential join of three or more distinctive graphs such as $G_1,G_2,\cdots ,G_n$ weobtain,

$C_c\left(G_1+G_2+\cdots +G_n\right)\le C_c\left(G_1\right)+C_c\left(G_2\right)+\cdots +C_c\left(G_n\right)$.

Proof: The distance from the center of the graph formed as a result of the series sum of $G_1,G_2,\cdots ,G_n$ graphs to all other vertices is at most one, or the newly formed graph becomes self-centered graph. In this case, the center coloring number of this sum will be smaller than the sum of the individual center coloring number.

Theorem 2.9: Consisting of the product of two self-centered graphs the center coloring number is one.

Proof: It is a self-centered graph in the product of two self-centered graphs [5]. From theorem 1.1 the center coloring number of a new graph is one.

Theorem 2.10: $P_n$ is a path with n-vertices and $P_m$ is a path with m-vertices. The center coloring number of Cartesian product of $P_n\times P_m$ is

$C_c\left(P_n\times P_m\right)=\lceil \frac{n^2-2n-2m+9}{2}\rceil$.

Proof: The graph $P_n\times P_m$ has n.m vertices. If n.m is “odd number” its center is a single vertex. n.m vertices are degree of 2, 3 and 4. $\left(n-2\right)\left(m-2\right)$ of these vertices are 4 degrees. One of the 4 degree vertices is the central vertex. Half of the remaining vertices are $\frac{\left(n-2\right)\left(m-2\right)-1}{2}$ distances from the center. The distance of 3 degree vertices to the center are 1 more than 4-degree vertices and 2-degree vertices are 1 more than 3-degree vertices. And also one color is needed for central vertex.

So

$C_c\left(P_n\times P_m\right)=\frac{\left(n-2\right)\left(m-2\right)-1}{2}+3=\frac{n^2-2n-2m+9}{2}$ (1)

If n.m is even number, the graph has 2-center vertices and

$C_c\left(P_n\times P_m\right)=\lceil \frac{n^2-2n-2m+9}{2}\rceil$ (2)

From (1) and (2) $C_c\left(P_n\times P_m\right)=\lceil \frac{n^2-2n-2m+9}{2}\rceil$.

Theorem 2.11: Let $G_n$ and $G_m$ are connected graphs. Using the Cartesian product we obtain,

$C_c\left(K_n\times K_m\right)\le C_c\left(G_n\times G_m\right)\le C_c\left(P_n\times P_m\right)$.

Proof: To verify the lower bound, it is clear by theorem 2.9. Because, if $G_n\times G_m$ is a self-centered graph, its center coloring number is 1. So $C_c\left(G_n\times G_m\right)$ is at least 1.

To verify the upper bound, the center coloring number of paths is more than well-known classes of graphs. The upper limit is the product of at least two path graphs, as the graph of the product of two path graphs grows.

3. Conclusion

In this paper, we have studied the center coloring number of different graph operations and apply our results to find bounds of some common graph families’ operations. However, there are still many other graph operations and special classes of graphs which are not covered here. So, for further research, center coloring of various other graph operations and composite graphs can be considered.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Yorgancioglu, Z., Dundar, P. and Berberler, M. E. (2015) The Center Coloring of a Graph. Journal of Discrete Mathematical Sciences, 18, 531-540.
[2]	Buckley, F. and Harary, F. (1990) Distance in Graph. Addison-Wesley, California, 335.
[3]	Chartrand, G. and Lesniak, L. (2005) Graphs & Digraphs. Chapman & Hall/CRC Press, USA, 386.
[4]	Gutman, I. (1998) Distance of Thorny Graphs. Publications de I’Institut Mathematique, 63, 31-36.
[5]	Dündar, P. (2004) The Median and Distance Measures of Celf-Centered Graphs. Journal of Engineering and Science, Sigma, 4, 229-233.