Volume 11, Number 10, July 2021

The Colored Disconnection Numbers of Cellular and Grid Networks

  Authors

Xuqing Bai and Xueliang Li and Yindi Weng, Center for Combinatorics and LPMC Nankai University, China

  Abstract

Let G be a nontrivial link-colored connected network. A link-cut R of G is called a rainbow link-cut if no two of its links are colored the same. A link-colored network G is rainbow disconnected if for every two nodes u and v of G, there exists a u-v rainbow link-cut separating them. Such a link coloring is called a rainbow disconnection coloring of G. For a connected network G, the rainbow disconnection number of G, denoted by rd(G), is defined as the smallest number of colors that are needed in order to make G rainbow disconnected. Similarly, there are some other new concepts of network colorings, such as proper disconnection coloring, monochromatic disconnection coloring and rainbow node-disconnection coloring. In this paper, we obtain the exact values of the rainbow (node-)disconnection numbers, proper and monochromatic disconnection numbers of cellular networks and grid networks, respectively.

  Keywords

link- (node-)coloring, connectivity, rainbow link- (node-)cut, (strong) rainbow (node-)disconnection numbers, proper and monochromatic disconnection numbers, cellular network, grid network.