Multi-color Forcing in Graphs
- PDF / 601,057 Bytes
- 14 Pages / 439.37 x 666.142 pts Page_size
- 42 Downloads / 187 Views
(0123456789().,-volV)(0123456789().,-volV)
ORIGINAL PAPER
Multi-color Forcing in Graphs Chassidy Bozeman1 • Pamela E. Harris2 • Neel Jain2 • Ben Young2 Teresa Yu2
•
Received: 4 December 2019 / Revised: 31 May 2020 Ó Springer Japan KK, part of Springer Nature 2020
Abstract Let G ¼ ðV; EÞ be a finite connected graph along with a coloring of the vertices of G using the colors in a given set X. In this paper, we introduce multi-color forcing, a generalization of zero-forcing on graphs, and give conditions in which the multicolor forcing process terminates regardless of the number of colors used. We give an upper bound on the number of steps required to terminate a forcing procedure in terms of the number of vertices in the graph on which the procedure is being applied. We then focus on multi-color forcing with three colors and analyze the end states of certain families of graphs, including complete graphs, complete bipartite graphs, and paths, based on various initial colorings. We end with a few directions for future research. Keywords Zero forcing Multicolor forcing
Mathematics Subject Classification 05C15 05C57
& Pamela E. Harris [email protected] Chassidy Bozeman [email protected] Neel Jain [email protected] Ben Young [email protected] Teresa Yu [email protected] 1
Department of Mathematics and Statistics, Mount Holyoke College, South Hadley, MA 01075, USA
2
Department of Mathematics and Statistics, Williams College, Williamstown, MA 01267, USA
123
Graphs and Combinatorics
1 Introduction Let G ¼ ðV; EÞ be a connected graph with all vertices colored blue or white. If v is a blue vertex of G, then v forces a white vertex u to blue if and only if u is the only white vertex in the neighborhood of v. This procedure is called the color change rule [1]. Then the zero forcing process is the procedure of applying the color change rule until no more changes are possible. If S is an initial set of vertices that is colored blue such that the entire graph can be colored blue by applying the color change rule, then S is a zero forcing set. A main goal in the study of zero forcing on graphs is to determine the the minimum size of a zero forcing set, known as the zero forcing number of a graph. The zero forcing procedure was introduced in linear algebra as a tool for studying the maximum nullity over a family of matrices [1], and independently in physics, computer science, and network science [2, 4, 6]. Since its introduction it has motivated the research of many mathematicians [3, 7, 9]. Kalinowski et al. considered bipartite, random, and pseudorandom graphs and established bounds for the zero forcing number of these graphs [10]. Chilakamarri et al. defined the iteration index of a graph to be the number of implementations of the color change rule, such that all vertices of a graph are blue. In their work, Chilakamarri et al. determined that the minimum of iteration indices of all minimum zero forcing sets of G was a graph invariant, which they called the iteration index of G [5]. Hogben et al. characterized
Data Loading...
