On the class of graphs ZP

Abstract

The following research was primarily focused on the class of graphs denoted by ZP. Let G = (V,E) be a graph made up of vertices V and edges E. The path cover number and zero forcing number are two graph parameters that have been of recent research interests and are closely related. Zero forcing at it’s most rudimentary, is a graph colouring game. There is a significant preexisting body of work on zero forcing, which includes relations between zero forcing and path cover numbers (denoted by Z(G) and P(G), respectively), as well as a relation between zero forcing and a notion of maximum nullity of a graph. One natural question along these lines that emerged was to impose equality conditions between Z(G) and P(G), and assuming these equality constraints hold for both G and all induced subgraphs of G, what class of graphs might arise and what is special about said graphs? Thus, we study the class ZP in which the zero forcing number and the path cover number are equal over all induced subgraphs. As many graphs are known to belong to ZP, such a trees, cycles, and cacti, these graphs are an excellent starting point for study. Hence, the cycle graph, denoted by Cn, provide the primary point of study early on in the research process. As Cn is a graph known to belong to ZP, we add interior chords to the cycle graph in many different orientations and in many numbers, then examine the resulting changes in both Z(G) and P(G). We then consider analyzing graphs that belong to ZP by conditioning on possible values of the path cover number, namely assuming P(G) = 2 and P(G) = 3. Finally, graph operations and their effect on graphs in ZP are considered. Of particular importance are the vertex and edge-sum operations. Ultimately, we are able to prove that the vertex or edge-sums of graphs in ZP do indeed remain in the class ZP.