The Zero Forcing Number of Bipartite Graphs, 2013



The Zero Forcing Number of Bipartite Graphs
Material Type
Undergraduate Research
Mays, Leah
Additional Contributors
Narayan, Sivaram
Copyright 2013 by Leah Mays. In accordance with Title 17 of the United States Code, Copyright Law of the United States of America, this material is copyrighted, and any further reproduction is prohibited without the permission of the copyright owner.
Non peer-reviewed;
Graph theory is the study of certain mathematical objects called graphs. A graph consists of points, called vertices, which are connected by line segments or arcs called edges. Graphs are commonly used to represent situations found in real life. In this project we color the vertices of a graph either black or white. We use the following basic color change rule: If a white vertex is the only white vertex adjacent to a black vertex, then we change the color of that white vertex to black. We start by coloring some vertices white and some vertices black. The goal is to find the minimum number of black vertices so that all white vertices are changed to black by a repeated application of the basic color change rule. The zero forcing number of a graph G, Z(G), is the minimum number of vertices to be colored black at the start so that all vertices become black by repeated use of the basic color change rule. There is a related notion called the semidefinite zero forcing number where the semidefinite color change rule is slightly different from the basic color change rule. In this project we find the zero forcing number and semidefinite zero forcing number of an important class of graphs called bipartite graphs. Faculty Advisor:Narayan, Sivaram, Department of Mathematics.
Select a page in the document viewer.