The Flood Polynomial of a Graph Karin R. Saoub, Michael Weselcouch, Trey Wilhoit, Jackson Wills Abstract . The flood polynomial of a simple finite graph is a weight generating function that counts all flooding cascade sets of the graph. The flood polynomial is inspired by the water mechanics in the video game Minecraft. We give necessary conditions for two graphs to have the same flood polynomial. We then provide a formula for the flood polynomials of certain families of graphs. We will see that many flood polynomials can be expressed using a Fibonacci-like recurrence and in some cases are equal to Fibonacci or Lucas polynomials. We then provide general examples of pairs of distinct graphs with the same flood polynomial. In these examples, the flood polynomial will be expressed as the product of Fibonacci and Lucas polynomials. 1. Introduction In this article, we introduce a graph polynomial, called the flood polynomial, which is based on the water mechanics in the video game Minecraft. The flood polynomial is a weight generating function that counts certain subsets of the vertices of a given graph. In Minecraft, water blocks and air blocks have an interesting relationship. If an air block is neighbors with two or more water blocks, then the air block will convert to water, allowing a player to convert a large region of air to water with only a few initial water blocks. Although regions in Minecraft must be contained in a grid, these flooding mechanics can be extended to general graphs. In this paper, we determine families of graphs which have flood polynomials that are products of Fibonacci polynomials and Lucas polynomials, providing a new combinatorial interpretation of a well-known identity involving Fibonacci and Lucas polynomials. We give an explicit formula for finding the flood polynomials of these graphs in terms of these products. This paper presents the first study of the flood polynomial, and we anticipate more results are possible beyond what is discussed in this article. This paper is organized as follows: in Section 2, we provide the necessary background, including the definitions of cascade sets and the flood polynomial; in Section 3, we discuss properties of a graph that can be determined by its flood polynomial; in Section 4, we give formulas for the flood polynomials of certain families of graphs; in Section 5, we provide examples of pairs of distinct graphs with the same flood polynomial; we conclude with presenting open questions in Section 6. 2. Preliminaries We begin with some preliminaries about compositions and partitions, graphs, flood sets, and the flood polynomial. For more information, see [ 11 ] . 2.1. Compositions and partitions A composition \alpha=(\alpha_{1},\alpha_{2},\dots,\alpha_{k}) of n is a finite sequence of positive integers summing to n . The compositions of n are in bijection with the subsets of [n-1] in the following way: for any composition \alpha , define D(\alpha)=\{\alpha_{1},\quad\alpha_{1}+\alpha_{2},\quad\dots,\quad\alpha_{1}+\alpha_{2}+\dots+\alpha_{k-1}\}\subseteq[n-1]. Likewise, for any subset S=\{s_{1},s_{2},\dots,s_{k-1}\}\subseteq[n-1] with s_{1}1 . Therefore, V-C is non-empty and contains no element that has two neighbors in C . This means C=C_{1} in the cascade sequence, hence C=\overline{C}\neq V . So C\notin\mathcal{F}(G) . Now suppose |G|=1 and C is a one-element cascade set. Since C is a subset of V and C and V have the same number of elements, they must be equal. Hence C\in\mathcal{F}(G) , as desired. ∎ Proposition 2.6 . If C\in\mathcal{F}(G) and C\subseteq C^{\prime} , then C^{\prime}\in\mathcal{F}(G) . Proof. For contradiction, let C be the set with the most elements such that C\in\mathcal{F}(G) and there exists C^{\prime}\supseteq C with C^{\prime}\notin\mathcal{F}(G) . Note that for this to be possible, |C||C| . Since C was picked to be the set with the most elements with the desired property, any superset of C_{1} necessarily floods G . We will now show that C_{1}^{\prime} is a superset of C_{1} . Let v\in C_{1} . If v\in C , then v\in C^{\prime} . If v\notin C , then v has two neighbors that are in C . Since C^{\prime}\supseteq C , this means that v has two neighbors that are in C^{\prime} . Therefore v\in C_{1}^{\prime} and C_{1}^{\prime}\in\mathcal{F}(G) and hence C^{\prime}\in\mathcal{F}(G) . This is a contradiction. Therefore if C\in\mathcal{F}(G) and C\subseteq C^{\prime} , then C^{\prime}\in\mathcal{F}(G) as desired. ∎ We say that a flooding cascade set C\in\mathcal{F}(G) is minimal if for all K\in\mathcal{F}(G) , K\subseteq C implies K=C . That is to say, if C is a minimal flooding cascade set, then no proper subset of C is a flooding cascade subset. Note that a graph can have minimal flooding cascade sets of different sizes. For example, consider the path graph with five vertices. This graph has two minimal flooding cascade sets, one with three elements and one with four elements as we see in the following example. Example 2.7 . The two minimal flooding sets for the path graph with five vertices are shown below. Notice that they are sets of different sizes. We can see that no proper subset of either of these cascade sets will flood the graph. There is no relation between the number of vertices in a graph and the size of its minimal flooding sets. We will see in the following example, for all n\geq 2 , there are graphs that have two-element flooding cascade sets. Let K_{n} denote the complete graph with n vertices and let C be any two vertices of K_{n} . Since every vertex that’s not in C is neighbors with both elements of C , C_{1} contains every vertex. Example 2.8 . Consider K_{6} shown below. We can see that every unflooded vertex is neighbors with both elements of the cascade set, so all unflooded vertices in K_{6} will immediately flood. The diameter of a graph is the the length of the shortest path between the most distanced vertices. In the case of the complete graph, the diameter is 1 since every pair of vertices share an edge. The example below illustrates that a graph with a two-element flooding cascade set can have an arbitrarily large diameter. Example 2.9 . The graph T_{n} (see Section 4.3 for a discussion of this family of graphs) has a diameter of \lfloor\frac{n}{2}\rfloor , but has a two-element flooding cascade set, C=\{v_{1},v_{2}\} . v_{1} v_{2} v_{3} v_{4} v_{n-2} v_{n-1} v_{n} C: \dots \dots We can see that v_{3} is neighbors with both v_{1} and v_{2} , so v_{3}\in C_{1} . Similarly, v_{4} is an element of C_{2} , and eventually, v_{n}\in C_{n-2}. v_{1} v_{2} v_{3} v_{4} v_{n-2} v_{n-1} v_{n} C_{1}: \rightarrow\cdots \dots v_{1} v_{2} v_{3} v_{4} v_{n-2} v_{n-1} v_{n} C_{n-3}: \dots \dots We give a general classification of the flood set of T_{n} in Lemma 4.19 . 2.4. Flood Polynomial Now that we have established some basic properties of flooding cascade sets, we introduce our main area of study. Definition 2.10 . The flood polynomial of a graph G , denoted by F_{G}(x) , is defined by F_{G}(x)=\sum_{C\in\mathcal{F}(G)}x^{|C|}. Since all flooding cascade sets are subsets of the vertices of G , it follows that for all k>n , the coefficient of x^{k} in F_{G}(x) is 0. Therefore F_{G}(x) is indeed a polynomial and its degree is at most n . In fact we will see that the degree of F_{G}(x) is equal to n (see Proposition 3.2 ). We can write F_{G}(x) as \displaystyle F_{G}(x)=\sum_{k=0}^{n}c_{k}x^{k} , where c_{k} is the number of k -element flooding cascade sets of G . The following result follows directly from the fact that flooding cascade sets are subsets of the vertices of G . Proposition 2.11 . If G is a graph with n vertices and \displaystyle F_{G}(x)=\sum_{k=0}^{n}c_{k}x^{k} , then 0\leq c_{k}\leq\binom{n}{k} . Example 2.12 . Let G be the following graph. It follows from the flood set shown in Example 2.4 , that F_{G}(x)=x^{4}+4x^{3}+2x^{2}. Proposition 2.13 . If G is the disjoint union of graphs H and K , i.e. G=H\oplus K , then F_{G}(x)=F_{H}(x)\cdot F_{K}(x) . Proof. Suppose C is a cascade set of G and let C|_{H} be the elements of C that are in H . Similarly, let C|_{K} be the elements of C that are in K . Since there are no edges between vertices in H and vertices in K , then C\in\mathcal{F}(G) if and only if C|_{H}\in\mathcal{F}(H) and C|_{K}\in\mathcal{F}(K) . ∎ 3. Properties determined by the flood polynomial In this section, we discuss graph properties that can be determined by its flood polynomial. We state necessary conditions for two graphs to have the same flood polynomials and some properties that cannot be determined by the flood polynomial. The first observation follows directly from the fact that the vertex set of a graph is a maximum size flooding cascade set. Proposition 3.1 . The number of vertices of G is determined by F_{G}(x) . The next property follows immediately from Definition 2.10 . Proposition 3.2 . The size of \mathcal{F}(G) determined by F_{G}(x) . Proof. It follows from the definition of F_{G}(x) that |\mathcal{F}(G)|=F_{G}(1) . ∎ While it may be reasonable to expect that the number of minimal flooding cascade sets of G may be determined by \mathcal{F}(G) , the following example demonstrates this not to be the case. Additionally, the number of elements in each minimal flooding cascade sets cannot be determined by \mathcal{F}(G) . Example 3.3 . We will see in Section 5.1 that the following graphs both have x^{8}+6x^{7}+10x^{6}+4x^{5} as their flood polynomial, but not the same number of minimal flooding cascade sets. P_{8}: P_{4}\oplus O_{4}: The five minimal flooding cascade sets of P_{8} are: The four minimal flooding cascade sets of P_{4}\oplus O_{4} are: While the flood polynomial of a disconnected graph is the product of the flood polynomials of each component of the graph (see Proposition 2.13 ), the previous example illustrates that the number of components of a graph is not determined by the flood polynomial. In fact, the following example gives the smallest case in which two graphs have the same flood polynomial, but different numbers of components. Example 3.4 . The following graphs have a flood polynomial equal to x^{2} , but different numbers of components. P_{2}: P_{1}\oplus P_{1}: In Section 5 we will give families of connected graphs who share flood polynomials with disconnected graphs. 3.1. Isolated points, leaves, and triggers A vertex is called an isolated point if it has no neighbors. It is called a leaf if it has exactly one neighbor. The total number of isolated points and leaves in the each of the graphs in Example 3.4 is two. The result below demonstrates that graphs with the same flood polynomials also have the same number of leaves and isolated points. Theorem 3.5 . If \displaystyle F_{G}(x)=\sum_{k=0}^{n}c_{k}x^{k} , then the total number of isolated points and leaves is n-c_{n-1} . Proof. Let L be the total number of isolated points and leaves in G . We want to show that L=n-c_{n-1} . Note that n-c_{n-1} is the number of (n-1) -element non-flooding cascade sets of G . This is because the total number of (n-1) -element cascades sets (flooding or non-flooding) of G is \binom{n}{n-1}=n and c_{n-1} is the number of (n-1) -element flooding cascade sets. Therefore, if we show that an (n-1) -element cascade set is flooding if and only if it contains all of the isolated points and leaves of G , then we have proven the result since that would imply that the number of (n-1) -element non-flooding cascade sets is equal to \binom{L}{1}=L . Suppose C is a cascade set with n-1 elements and suppose v is the vertex that is not in C . If v is an isolated point or a leaf, then it does not have two neighbors in C , so v\notin C_{1} and C=C_{1} . Therefore \overline{C}\neq V and C\notin\mathcal{F}(G) . There are L different possibilities for v in this case. If v is not an isolated point or leaf, then it does have two neighbors in C . Therefore v\in C_{1} and C_{1}=V . Hence C\in\mathcal{F}(G) . Therefore the number of (n-1) -element non-flooding cascade sets is equal to the number of vertices that are isolated points or leaves. ∎ Corollary 3.6 . The total number of isolated points and leaves of G is determined by F_{G}(x) . The following result follows from the proof of Theorem 3.5 . Corollary 3.7 . If C\in\mathcal{F}(G) , then C contains all of G ’s isolated points and leaves. We now turn our attention to certain two-element subgraphs, which provide a natural way to extend our results about leaves and isolated points. Definition 3.8 . A trigger is a set of two vertices \{v_{i},v_{j}\} , where v_{i} and v_{j} share an edge and both have degree 2. Before proving that the flood polynomial determines the number of triggers, we consider the following example to solidify the concept of a trigger. Example 3.9 . The following graph contains two triggers, \{v_{1},v_{4}\} and \{v_{3},v_{4}\} . v_{1} v_{2} v_{3} v_{4} v_{5} Even though v_{1} and v_{3} both have degree two, \{v_{1},v_{3}\} is not a trigger since v_{1} and v_{3} are not neighbors. Triggers play an important role in determining whether a cascade set completely floods the graph, as shown below. Lemma 3.10 . Let u and v be vertices of degree at least 2 and let C=V-\{u,v\} . Then C\in\mathcal{F}(G) if and only if \{u,v\} is not a trigger. Proof. Let C be a cascade set of G . If \{u,v\} is a trigger, then u and v are neighbors and they each have one other neighbor in the graph. This means u\notin C_{1} and v\notin C_{1} since neither one has two neighbors in C . Therefore C=C_{1} and C\notin\mathcal{F}(G) . If \{u,v\} is not a trigger, then either u and v are not neighbors, or u and v are neighbors with at least one with degree greater than 2 (our assumption is that u and v are not isolated points or leaves). Suppose that u and v are not neighbors. Since they both have degree at least 2 , it follows that they both have 2 neighbors in C . Therefore C_{1}=V and C\in\mathcal{F}(G) . Now suppose without loss of generality that that u and v are neighbors but the degree of u is greater than 2. This means that u has at least 2 neighbors in C so u\in C_{1} . Since u\in C_{1} and v has at least one neighbor in C , it follows that v\in C_{2} and C_{2}=V . Therefore C\in\mathcal{F}(G) . ∎ Combining this result with the contrapositive of Proposition 2.6 gives the following. Corollary 3.11 . If C is a cascade set and V-C contains a trigger, then C\notin\mathcal{F}(G) We are now ready to state how to enumerate triggers from the flood polynomial. Theorem 3.12 . If \displaystyle F_{G}(x)=\sum_{k=0}^{n}c_{k}x^{k} , then the total number of triggers is \displaystyle\binom{n}{2}-(n-1)(n-c_{n-1})+\binom{n-c_{n-1}}{2}-c_{n-2} . Proof. The structure of this proof will be very similar to that of Theorem 3.5 . Let T be the number of triggers in G . We will show T+(n-1)(n-c_{n-1})-\binom{n-c_{n-1}}{2}=\binom{n}{2}-c_{n-2} . Note that the right hand side, \binom{n}{2}-c_{n-2} , is the number of (n-2) -element non-flooding cascade sets. Also note that by Theorem 3.5 and the property of inclusion-exclusion, (n-1)(n-c_{n-1})-\binom{n-c_{n-1}}{2} is the number of (n-2) -element cascade sets C such that V-C contains at least one leaf or isolated point. Note that for all these sets, V-C is not a trigger because the vertices that make up triggers have degree 2 . We have already established by Corollary 3.7 that these cascade sets are non-flooding. We also established by Lemma 3.10 that the only other (n-2) -element non-flooding cascade sets are in bijection with the set of triggers. Therefore we have that T+(n-1)(n-c_{n-1})-\binom{n-c_{n-1}}{2}=\binom{n}{2}-c_{n-2} as desired. ∎ Corollary 3.13 . The total number of triggers of G is determined by F_{G}(x) . As seen in this section, the values of c_{n} , c_{n-1} , and c_{n-2} can be used to determine properties about the graph. It is still not known whether the value of any other coefficients can be used to determined the number of other subgraphs of G similar to what we saw in Theorem 3.5 and Theorem 3.12 . 3.2. Free vertices We saw in the proof of Corollary 3.7 that if a graph contains any leaves or isolated points, then any flooding cascade set must contain all of those vertices. In particular, the minimal flooding cascade sets must contain all of the leaves and isolated points. On the other hand, it is possible that the inclusion of a vertex in a cascade set is never necessary to flood the graph. We say a vertex v is free if it is not an element of any minimal flooding cascade sets. Proposition 3.14 . If a vertex v is neighbors with two or more leaves, then v is free. Proof. Suppose v is a vertex with at least two leaves as neighbors and suppose that v is an element of the flooding cascade set C . We will prove this result by showing that C is not a minimal flooding cascade set. By Corollary 3.7 , we know that C contains all of the leaves of the graph. In particular, C contains at least two neighbors of v . Let C^{\prime}=C-\{v\} . Since C^{\prime} contains at least two neighbors of v , we have that v\in C_{1}^{\prime} so C\subseteq C_{1}^{\prime} . By Proposition 2.6 , it follows that C_{1}^{\prime}\in\mathcal{F}(G) so C^{\prime}\in\mathcal{F}(G) . Therefore C is not minimal since C^{\prime}\subsetneq C , as desired. ∎ We just saw that any vertex with two or more leaves as neighbors is necessarily free, however, there are other, less trivial ways for a vertex to be free. Example 3.15 . The following graph has two free vertices, but neither of them has two leaves as neighbors. The free vertices are colored black. Observe that neither of those two vertices appear in the the two minimal flooding cascade sets shown below. It is trivial that F_{G}(x) gives an upper bound for the number of free vertices of G since F_{G}(x) gives the total number of vertices. However, a stronger upper bound can be determined from F_{G}(x) . Theorem 3.16 . The number free vertices of G is bounded above by the number of factors of (x+1) in F_{G}(x) . Proof. Let \mathcal{S} be the set of free vertices of G , s=|\mathcal{S}| , and let \mathcal{P}(\mathcal{S}) be the power set of \mathcal{S} . We want to show that (x+1) is a factor of F_{G}(x) with degree at least s . Let \mathcal{M}=\{C\in\mathcal{F}(G)\mid C\cap\mathcal{S}=\varnothing\} , i.e., \mathcal{M} is the set of all flooding cascade sets of G that contain no free vertices. By definition of a free vertex, every minimal flooding cascade set is an element of \mathcal{M} . Let \mathcal{A}=\{M\cup S\mid M\in\mathcal{M}\text{ and }S\in\mathcal{P}(\mathcal{S})\} . We will show that \mathcal{F}(G)=\mathcal{A} . Let M\in\mathcal{M} and S\in\mathcal{P}(\mathcal{S}) . Since every element of \mathcal{M} is a flooding cascade set, then by Proposition 2.6 , we have that (M\cup S)\in\mathcal{F}(G) . Therefore \mathcal{A}\subseteq\mathcal{F}(G) . If C\in\mathcal{F}(G) , then to show C\in\mathcal{A} , we need to show that (C-\mathcal{S})\in\mathcal{M} . Since C\in\mathcal{F}(G) there exists a minimal flooding cascade set M such that M\subseteq C . It follows that M=(M-\mathcal{S})\subseteq(C-\mathcal{S}) . Therefore C-\mathcal{S} is a flooding cascade set that contains no free vertices. Hence C\in\mathcal{A} and \mathcal{F}(G)\subseteq\mathcal{A} . It follows that F_{G}(x)=\sum_{\begin{subarray}{c}M\in\mathcal{M},\\ S\in\mathcal{P{(\mathcal{S})}}\end{subarray}}x^{|M|+|S|}=\sum_{M\in\mathcal{M}}x^{|M|}\cdot\sum_{S\in\mathcal{P(S)}}x^{|S|}=\sum_{M\in\mathcal{M}}x^{|M|}(x+1)^{s} as desired. ∎ The graph from Example 3.15 has a flood polynomial that factors as x^{3}(x+2)(x+1)^{2} and it has 2 free vertices. In general, the inequality given in Theorem 3.16 will not reduce to an equality. In fact, the following example shows that the number of free vertices is not determined by the flood polynomial. Example 3.17 . The following graphs have x^{4}(x+1)(x+3) as their flood polynomial, but a different number of free vertices. The free vertex is colored black. P_{6}: P_{3}\oplus C_{3}: Even though F_{P_{6}}(x) has a factor of (x+1) , P_{6} has no free vertices as you can see by the minimal flooding cascade sets shown below. 4. Flood Polynomials for Families of Graphs In this section we state a formula for the flood polynomials for three families of graphs: parallel paths, cycles, and triangle mosaics. 4.1. Parallel Paths A parallel path graph of size m\times n is a graph with m\cdot n vertices, denoted P_{m,n} . It is the graph with vertex set V(P_{m,n})=\{v_{i,j}\mid 1\leq i\leq m\text{ and }1\leq j\leq n\} and edge set E(P_{m,n})=\{v_{i,j}v_{i,j+1}\mid 1\leq j1 and the result holds for all P_{2,k} where 1\leq k2 is unknown. The following example demonstrates why this question is hard, even when m=3 . Example 4.12 . The following cascade set satisfies the parallel path property as well as conditions similar to those stated in Lemma 4.8 , but it does not flood the graph. 4.2. Cycle A Cycle Graph with n\geq 3 vertices, denoted O_{n} is the graph with vertex set V(O_{n})=\{v_{1},\dots,v_{n}\} and edge set E(O_{n})=\{v_{1}v_{2},\dots,v_{n-1}v_{n},v_{n}v_{1}\}. It follows immediately from construction that O_{n} is connected and each vertex has degree 2 . Before providing a recursion for the flood polynomial of O_{n} , we begin with some results about the properties of the flooding cascade sets of O_{n} . Proposition 4.13 . Every neighboring pair of vertices in O_{n} forms a trigger. Proof. Suppose we have a neighboring pair of vertices \{v_{x},v_{y} }. Since each vertex has degree 2 , it follows from Definition 3.8 that v_{x} and v_{y} form a trigger as desired. ∎ Lemma 4.14 . Let C be a cascade set of G=O_{n} . Then C\in\mathcal{F}(G) if and only if V-C contains no triggers. Proof. Suppose C is a cascade set of O_{n} and suppose that V-C contains no triggers. We want to show that C\in\mathcal{F}(O_{n}) . We will show this by showing that v\in C_{1} for all v\in V . If v\in C , then this case is trivial as v\in C implies v\in C_{1} . If v\notin C , then because V-C contains no triggers, both of v ’s neighbors are in C . Therefore v\in C_{1} since it has two neighbors in C . Therefore, if V-C contains no triggers, then C\in\mathcal{F}(O_{n}) . If V-C contains a trigger, then by Corollary 3.11 , C will not flood O_{n} . ∎ We say that any cascade set of O_{n} that satisfies the conclusions of Lemma 4.14 has the cycle flood property . We now give a recursion for the flood polynomial of cycle graphs. Theorem 4.15 . The flood polynomial for cycle graphs can be determine recursively with F_{O_{3}}(x)=x^{3}+3x^{2} , F_{O_{4}}(x)=x^{4}+4x^{3}+2x^{2} , and for n\geq 5 , F_{O_{n}}(x)=x\cdot F_{O_{n-1}}(x)+x\cdot F_{O_{n-2}}(x) . Proof. The elements of \mathcal{F}(O_{3}) are \{v_{1},v_{2}\},\{v_{2},v_{3}\} , \{v_{1},v_{3}\} and \{v_{1},v_{2},v_{3}\} . Therefore F_{O_{3}}(x)=x^{3}+3x^{2} . The elements of \mathcal{F}(O_{4}) are the cascade sets shown in Example 2.4 . Therefore F_{O_{4}}(x)=x^{4}+4x^{3}+2x^{2} . Now let n\geq 5. We will show that F_{O_{n}}(x)=x\cdot F_{O_{n-1}}(x)+x\cdot F_{P_{n-2}}(x) by showing that each element of \mathcal{F}(O_{n}) can be expressed as the union of a single element with either an element of \mathcal{F}(O_{n-1}) or \mathcal{F}(O_{n-2}) . We will create a map between flooding cascade sets of O_{n} to those of O_{n-1} or O_{n-2} . Recall that from Lemma 4.14 , if C\in\mathcal{F}(O_{n}) , then it must contain at least one vertex of every neighboring pair in O_{n} . Applying the map will remove an element from C to create a flooding cascade set of either O_{n-1} or O_{n-2} . It will be clear which element was removed from C so the map can be reversed. Note that removing an element in C will decrease |C| by 1 , thus accounting for the factor of x in the equation. We will keep these facts in mind as we proceed with the proof. We begin by considering v_{n} , with three possible cases for the status of v_{n} . Case 1: v_{n}\in C and \{v_{n-1},v_{1}\}\subseteq V-C . We can map this to the flooding cascade set C^{\prime} of O_{n-2} where C^{\prime}=C-\{v_{n-1},v_{n}\} . Note that since C floods O_{n} , C has the cycle flood property. This means that C contains at least one element of every neighboring pair of vertices of O_{n} . Since only one element of C is removed to form C^{\prime} we only need to verify that at least one of v_{n-2} and v_{1} is in C^{\prime} in order for C^{\prime} to have the cycle flood property. Since v_{n-1}\notin C , it follows that v_{n-2}\in C and hence v_{n-2}\in C^{\prime} as well. Therefore C^{\prime} has the cycle flood property and C^{\prime}\in\mathcal{F}(O_{n-2}) . This case accounts for all elements of \mathcal{F}(O_{n-2}) that do not contain v_{1} . Case 2: v_{n}\in C and \{v_{n-1},v_{1}\}\nsubseteq V-C . Then we will map C to the flooding cascade set C^{\prime} of O_{n-1} where C^{\prime}=C-\{v_{n}\} . As with the first case, C^{\prime} has only one fewer element than C . Note again that by Lemma 4.14 , C contains at least one element of every neighboring pair of vertices of O_{n} . Since only one element of C is removed to form C^{\prime} we only need to verify that at least one of v_{n-1} and v_{1} is in C^{\prime} in order for C^{\prime} to have the cycle flood property. We are assuming that \{v_{n-1},v_{1}\}\nsubseteq V-C so \{v_{n-1},v_{1}\}\nsubseteq V-C^{\prime} . Therefore C^{\prime} has the cycle flood property and C^{\prime}\in\mathcal{F}(O_{n-1}) . This case accounts for all elements of \mathcal{F}(O_{n-1}) . Case 3: v_{n}\notin C . From Lemma 4.14 , we have \{v_{n-1},v_{1}\}\subseteq C . Then we will map C to the flooding cascade set C^{\prime} of O_{n-2} where C^{\prime}=C-\{v_{n-1}\} . As with the first two cases, C^{\prime} has only one fewer element than C . Note again that by Lemma 4.14 , C contains at least one element of every neighboring pair of vertices of O_{n} . Since only one element of C is removed to form C^{\prime} we only need to verify that at least one of v_{n-2} and v_{1} is in C^{\prime} in order for C^{\prime} to have the cycle flood property. We are assuming that v_{1}\in C so v_{1}\in C^{\prime} . Therefore C^{\prime} has the cycle flood property and C^{\prime}\in\mathcal{F}(O_{n-2}) . This case accounts for all elements of \mathcal{F}(O_{n-2}) that contain v_{1} . Therefore, every flooding cascade set C\in O_{n} can be mapped to one of either O_{n-1} or O_{n-2} by removing one element from C . This gives us the recursion relationship F_{O_{n}}(x)=x\cdot F_{O_{n-1}}(x)+x\cdot F_{O_{n-2}}(x) as desired. ∎ The Lucas numbers are a sequence of number defined recursively by L_{0}=2 , L_{1}=1 , and for n\geq 2 , L_{n}=L_{n-1}+L_{n-2} ; the first few Lucas numbers are 2,1,3,4,7,11,\dots . The Lucas numbers count numerous combinatorial objects [ 8 ] , but in particular, for n\geq 3 , L_{n} is the number of independent vertex sets (a set of vertices in a graph where no two of which are adjacent) for the cycle graph O_{n} [ 10 ] . Note that Lemma 4.14 can be rewritten as C\in\mathcal{F}(O_{n}) if and only if V(O_{n})-C is an independent vertex set. Therefore \mathcal{F}(O_{n}) is in bijection with the set of independent vertex sets of O_{n} , leading to the following result enumerating the flood set of O_{n} . Corollary 4.16 . For n\geq 3 , |\mathcal{F}(O_{n})|=F_{O_{n}}(1)=L_{n} . There are many ways to define the Lucas polynomials , but one such definition is they are the polynomials defined recursively as L_{0}(x)=2 , L_{1}(x)=x , and for n\geq 2 , L_{n}(x)=x\cdot L_{n-1}(x)+x\cdot L_{n-2}(x) . It follows immediately from Theorem 4.15 that for n\geq 3 , F_{O_{n}}(x)=L_{n}(x) . We now give a combinatorial interpretation of the coefficients of L_{n}(x) in terms of flooding cascade sets of O_{n} . Corollary 4.17 . If n\geq 3 and L_{n}(x)=\sum_{k=0}^{n}L(n,k)x^{k} , then L(n,k) is the number k -element flooding cascade sets of O_{n} . 4.3. Triangle Mosaic A triangle mosaic graph of size n is a graph with n vertices, denoted T_{n} . The edge set of T_{n} is the graph with vertex set V(T_{n})=\{v_{1},\dots,v_{n}\} and edge set E(T_{n})=\{v_{i}v_{j}\mid|i-j|\leq 2\}. The following is the triangle mosaic graph of size 6 , T_{6} . v_{2} v_{1} v_{4} v_{3} v_{6} v_{5} We saw in Example 2.9 that all triangle mosaic graphs can be flooded with a two-element cascade set. Lemma 4.18 . Let C be a cascade set of G=T_{n} . If \{v_{k},v_{k+1}\}\subseteq C for some 1\leq k2 and the result holds for all T_{m} where 2\leq m1 , by induction C\cap\{v_{k},\dots,v_{n}\} floods this graph. Therefore C\in\mathcal{F}(G) as desired. ∎ Theorem 4.19 . Let C be a cascade set of G=T_{n} . Then C\in\mathcal{F}(G) if and only if there exists 1\leq i4 . This means that there is no element of V-C that is neighbors with at least two elements of C . Therefore C_{1}=C and C\notin\mathcal{F}(G) . ∎ We can now give a formula for the flood polynomial of T_{n} , but for convenience, let \textrm{COMP}(n,4) be defined as follows: \textrm{COMP}(n,4)=\{\alpha\vDash(n+1)\mid\alpha_{k}\leq 4\text{ for some }1|C| and C^{\prime}\in\mathcal{F}(G) , then C^{\prime}\in\mathcal{F}(G^{\prime}\oplus P_{3}) . Clearly |C|\neq n because if |C|=n , then C is trivially an element of \mathcal{F}(G^{\prime}\oplus P_{3}) . To avoid confusion, we will write C_{1}(G) for the first element in the flood sequence of C on the graph G . Since |C||C| . There are three cases to consider: x=v , x\in\{g_{1},\dots,g_{m}\} , or x is not a neighbor of v . If x=v , then x\in C_{1}(G^{\prime}\oplus P_{3}) because l_{m+1} and l_{m+2} are leaves so they must be in C . If x\in\{g_{1},\dots,g_{m}\} , the C contains at least one neighbor of x not equal to v . Without loss of generality we can say x=g_{1} . Since C contains at least one neighbor of x not equal to v and C contains l_{1} , we have that x\in C_{1}(G^{\prime}\oplus P_{3}). The final case to consider is x is not a neighbor of v . In this case, x\in C_{1}(G^{\prime}\oplus P_{3}) since the only new edges created in G^{\prime} involve v . Therefore if C\in\mathcal{F}(G) , then C\in\mathcal{F}(G^{\prime}\oplus P_{3}) . Now suppose for contradiction that there exists a flooding cascade set C\in\mathcal{F}(G^{\prime}\oplus P_{3}) such that C\notin\mathcal{F}(G) and we will assume that C is largest such set. That is to say if |C^{\prime}|>|C| and C^{\prime}\in\mathcal{F}(G^{\prime}\oplus P_{3}) , then C^{\prime}\in\mathcal{F}(G) . Clearly |C|\neq n because if |C|=n , then C is trivially an element of \mathcal{F}(G) . If v\notin C , then v\in C_{1}(G^{\prime}\oplus P_{3}) since l_{m+1} and l_{m+2} are leaves so they must be in C . Similarly, v\in C_{1}(G) . Note that C\cup\{v\}\in\mathcal{F}(G) since |C\cup\{v\}|>|C| and C_{1}(G)\supseteq C\cup\{v\} . So C_{1}(G)\in\mathcal{F}(G) and C\in\mathcal{F}(G) . Now suppose v\in C . Let x\in C_{1}(G^{\prime}\oplus P_{3})-C . It’s either the case that x\in\{g_{1},\dots,g_{m}\} or x is not a neighbor of v . If x\in\{g_{1},\dots,g_{m}\} , then without loss of generality we can say x=g_{1} . Then C contains at least one neighbor of x that is not equal to l_{1} and also contains v . Therefore x\in C_{1}(G) . If x is not a neighbor of v , then x\in C_{1}(G) since the only new edges created in G^{\prime} involve v . Therefore if C\in\mathcal{F}(G^{\prime}\oplus P_{3}) , then C\in\mathcal{F}(G) as desired. ∎ 5.1. Path graphs with an even number of vertices We now show that the flood polynomial for the path with 2n vertices has the same flood polynomial as the disjoint union of the path with n vertices with the cycle with n vertices. This will lead to an alternate proof of a well-known result about even-indexed Fibonacci polynomials that f_{2n}(x)=f_{n}(x)\cdot L_{n}(x) (see [ 2 ] ). Theorem 5.3 . For n\geq 3,F_{P_{2n}}(x)=F_{P_{n}}(x)\cdot F_{O_{n}}(x) . Proof. Recall that both \mathcal{F}(P_{2n}) and \mathcal{F}(P_{n}\oplus O_{n}) are sets of flooding cascade sets. We will create a bijection between \mathcal{F}(P_{2n}) and \mathcal{F}(P_{n}\oplus O_{n}) that preserves the size of the flooding cascade set. Once the bijection is established, the result follows immediately from Proposition 2.13 . Let \{v_{1},\dots v_{2n}\} be the set of vertices of P_{2n} and let \{a_{1},\dots a_{n}\}\cup\{b_{1},\dots b_{n}\} be the set vertices of P_{n}\oplus O_{n} . The edge set of P_{2n} is \{v_{1}v_{2},\dots v_{2n-1}v_{2n}\} and the edge set of P_{n}\oplus O_{n} is \{a_{1}a_{2},\dots a_{n-1}a_{n}\}\cup\{b_{1}b_{2},\dots b_{n-1}b_{n},b_{1}b_{n}\} . That is to say, the a vertices are the vertices of the path and the b vertices are the vertices of the cycle. Let us begin by mapping the flooding cascade sets in \mathcal{F}(P_{2n}) to those of F(P_{n}\oplus O_{n}) . Let C\in\mathcal{F}(P_{2n}) . Since P_{2n} is a path graph, by Theorem 4.4 we know that C has the parallel path property so both v_{1} and v_{2n} are in C and that for all 11 and F_{\textrm{CEN}{\beta}}(x)=(F_{P_{3}}(x))^{\ell(\beta)-1}\cdot\prod_{j=1}^{l(\beta)}F_{P_{\beta_{j}+1}}(x) whenever \ell(\beta)<\ell(\alpha) . Let \alpha^{\prime} be the composition defined by \alpha^{\prime}=(\alpha_{2},\cdots,\alpha_{\ell(\alpha)}) . Note that applying Lemma 5.1 with v=v_{\alpha_{1}+1} gives us that F_{\textrm{CEN}{\alpha}}(x)=F_{P_{3}}(x)\cdot F_{P_{\alpha_{1}+1}}(x)\cdot F_{\textrm{CEN}{\alpha^{\prime}}}(x). Since \ell(\alpha^{\prime})=\ell(\alpha)-1<\ell(\alpha) , we have that F_{\textrm{CEN}{\alpha^{\prime}}}(x)=(F_{P_{3}}(x))^{\ell(\alpha^{\prime})-1}\cdot\prod_{j=1}^{l(\alpha^{\prime})}F_{P_{\alpha^{\prime}_{j}+1}}(x)=(F_{P_{3}}(x))^{\ell(\alpha)-2}\cdot\prod_{j=2}^{l(\alpha)}F_{P_{\alpha_{j}+1}}(x). Hence F_{\textrm{CEN}{\alpha}}(x)=(F_{P_{3}}(x))^{\ell(\alpha)-1}\cdot\prod_{j=1}^{l(\alpha)}F_{P_{\alpha_{j}+1}}(x) as desired. ∎ Notice that the values of the entries of \alpha have an effect on the flood polynomial of \textrm{CEN}_{\alpha} , but the order in which they appear does not. Corollary 5.6 . If \alpha\sim\lambda and \beta\sim\lambda , then F_{\textrm{CEN}_{\alpha}}(x)=F_{\textrm{CEN}_{\beta}}(x) . Combining Theorem 5.5 with the results of Section 4.1.1 we get that the flood polynomial of centipede graphs is the product of Fibonacci polynomials and, as a result, the size of the flood set is a product of Fibonacci numbers. Corollary 5.7 . The number of flooding cascade sets of \textrm{CEN}_{\alpha} is a product of Fibonacci numbers. In particular |\mathcal{F}(\textrm{CEN}_{\alpha})|=f_{3}^{\ell(\alpha)-1}\cdot\prod_{j=1}^{l(\alpha)}f_{\alpha_{j}+1}. 5.3. Tick Graph A tick graph of size \alpha\vDash n for n\geq 3 is a graph with n+4\cdot(\ell(\alpha)) vertices, denoted \textrm{TICK}_{\alpha} . Let D=(D(\alpha)\cup\{n\}) . The tick graph \textrm{TICK}_{\alpha} is the graph with vertex set V(\textrm{TICK}_{\alpha})=\{v_{1},\dots,v_{n}\}\cup\{l_{d,1},\dots,l_{d,4}\mid d\in D\} and edge set E(\textrm{TICK}_{\alpha})=\{v_{1}v_{2},\dots,v_{n-1}v_{n},v_{n}v_{1}\}\cup\{v_{d}l_{d,1},\dots,v_{d}l_{d,4}\mid d\in D\}. In plain words, \textrm{TICK}_{\alpha} can be constructed by starting with an n -element cycle graph and then appending four leaves to v_{d} for all d\in D . \textrm{TICK}_{(2,2)}: Theorem 5.8 . The tick graph \textrm{TICK}_{\alpha} has the same flood polynomial as the disjoint union of 2\cdot\ell(\alpha) path graphs. In particular, F_{\textrm{TICK}{\alpha}}(x)=(F_{P_{3}}(x))^{\ell(\alpha)}\cdot\prod_{j=1}^{l(\alpha)}F_{P_{\alpha_{j}+1}}(x) Proof. Applying Lemma 5.1 with v=v_{n} gives F_{\textrm{TICK}{\alpha}}(x)=F_{P_{3}}\cdot F_{\textrm{CEN}{\alpha}}(x). It follows from Theorem 5.5 that F_{\textrm{TICK}{\alpha}}(x)=(F_{P_{3}}(x))^{\ell(\alpha)}\cdot\prod_{j=1}^{l(\alpha)}F_{P_{\alpha_{j}+1}}(x). ∎ As with the case of the centipede graph, the values of the entries of \alpha have an effect on the flood polynomial of \textrm{TICK}_{\alpha} , but the order in which they appear does not. Corollary 5.9 . If \alpha\sim\lambda and \beta\sim\lambda , then F_{\textrm{TICK}_{\alpha}}(x)=F_{\textrm{TICK}_{\beta}}(x) . Combining Theorem 5.8 with the results of Section 4.1.1 we get that the flood polynomial of tick graphs is the product of Fibonacci polynomials and as a result, the size of the flood set is a product of Fibonacci numbers. Corollary 5.10 . The number of flooding cascade sets of \textrm{TICK}_{\alpha} is a product of Fibonacci numbers. In particular |\mathcal{F}(\textrm{TICK}_{\alpha})|=f_{3}^{\ell(\alpha)}\cdot\prod_{j=1}^{l(\alpha)}f_{\alpha_{j}+1}. It follows immediately from the proof of Theorem 5.8 , that every tick graph has the same flood polynomial as the disjoint union of a three-element path graph with a centipede graph. Corollary 5.11 . If \alpha\sim\lambda and \beta\sim\lambda , then F_{\textrm{TICK}_{\alpha}}(x)=F_{P_{3}}(x)\cdot F_{\textrm{CEN}{\beta}}(x) . 6. Discussion and Open Questions We conclude this article with some open questions, the difficulty of which remain unclear. Question 6.1 . Can the results of Section 3.1 be generalized to determine the number of certain three-element subgraphs of G from F_{G}(x) ? Question 6.2 . Since F_{P_{n}}(x) is a Fibonacci polynomial, it is well-known that if m divides n , then F_{P_{m}}(x) divides F_{P_{n}}(x) [ 3 ] . For what m and n does there exist a graph H where F_{P_{n}}(x) = F_{P_{m}}(x)\cdot F_{H}(x) ? The case where n=2m is Theorem 5.3 . When m=3 and n=9 , there is no such graph. Question 6.3 . For what polynomials p(x) does there exist a graph G such that F_{G}(x)=p(x) . We know from Proposition 2.11 some necessary conditions that the coefficients of p(x) must satisfy, but can these polynomials be completely classified? In [ 1 ] , the authors introduce chainsaw graphs and broken chainsaw graphs. They proved that the number of independent vertex sets of these graphs is enumerated by generalized Fibonacci and Lucas numbers. We saw in Section 4.1.1 and Section 4.2 that the independent vertex sets of path graphs and cycle graphs are closely related to the flooding cascade sets. Chainsaw and broken chainsaw graphs are natural generalizations of cycle graphs and path graphs, respectively. Question 6.4 . Is there a recursive formula for the flood polynomial of chainsaw graphs or broken chainsaw graphs that generalize the results of Section 4.1.1 and Section 4.2 ? 7.