0
\$\begingroup\$

Reference: arXiv:2504.04233

Example 2.12: 4-vertex cycle graph

  • Structure: Square graph with 4 vertices
  • Flooding cascade sets: 7 total (2 of size 2, 4 of size 3, 1 of size 4)
  • Key insight: Opposite vertices {1,3} or {2,4} can flood the entire cycle
  • Flood polynomial: F_G(x) = x⁴ + 4x³ + 2x² ✅ Verified

Example 3.3: Identical flood polynomials, different minimal sets

  • P₈ (path): 5 minimal flooding cascade sets
  • P₄⊕O₄ (path+cycle): 4 minimal flooding cascade sets
  • Both have: F_G(x) = x⁸ + 6x⁷ + 10x⁶ + 4x⁵ ✅ Verified
  • Key insight: Same polynomial, different structural properties

Example 3.17: Identical flood polynomials, different free vertices

  • P₆ (path): 0 free vertices
  • P₃⊕C₃ (path+cycle): 1 free vertex (vertex 2)
  • Both have: F_G(x) = x⁶ + 4x⁵ + 3x⁴ = x⁴(x+1)(x+3) ✅ Verified
  • Key insight: Factor (x+1) gives upper bound, not exact count

Fundamental Mathematical Discoveries

The computational verification demonstrates three critical limitations of flood polynomials:

  1. Non-uniqueness: Different graphs can have identical flood polynomials
  2. Structural ambiguity: Same polynomial doesn't determine graph connectivity
  3. Property limitations: Flood polynomials don't uniquely determine:
  • Number of minimal flooding cascade sets - Number of free vertices - Specific graph structure

Technical Achievement

The implementation successfully:

  • ✅ Computed cascade sequences using flooding rules
  • ✅ Identified all flooding cascade sets for each graph
  • ✅ Calculated flood polynomials exactly matching theoretical predictions
  • ✅ Detected free vertices using the mathematical definition
  • ✅ Verified polynomial factorizations

You may try the code online!

(* Flood Polynomial Examples from "The Flood Polynomial of a Graph" *)
(* Reproducing Definition 2.10, Example 2.12, and Example 3.3 *)

(* Clear all variables *)
Clear["Global`*"]

(* Definition 2.10: Flood Polynomial
   The flood polynomial of a graph G, denoted F_G(x), is defined by
   F_G(x) = Sum over all flooding cascade sets C of x^|C|
*)

Print["=== Definition 2.10: Flood Polynomial ==="]
Print["The flood polynomial F_G(x) = Sum_{C in F(G)} x^|C|"]
Print["where F(G) is the set of all flooding cascade sets of graph G"]
Print[""]

(* Helper function to generate all subsets of a list *)
allSubsets[list_] := Subsets[list]

(* Helper function to check if a vertex has at least two neighbors in a cascade set *)
hasAtLeastTwoNeighbors[vertex_, cascadeSet_, adjacencyList_] :=
  Length[Intersection[cascadeSet, adjacencyList[vertex]]] >= 2

(* Function to simulate cascade sequence *)
cascadeSequence[initialSet_, adjacencyList_, vertices_] :=
  Module[{current = initialSet, next, iterations = 0, maxIter = Length[vertices] + 5},
   While[iterations < maxIter,
    next = Union[current,
      Select[vertices, hasAtLeastTwoNeighbors[#, current, adjacencyList] &]];
    If[next == current, Break[]];
    current = next;
    iterations++
    ];
   current
   ]

(* Function to check if a cascade set floods the entire graph *)
isFloodingCascadeSet[cascadeSet_, adjacencyList_, vertices_] :=
  cascadeSequence[cascadeSet, adjacencyList, vertices] == vertices

(* Function to compute flood polynomial *)
floodPolynomial[adjacencyList_, vertices_] :=
  Module[{allSets, floodingSets, polynomial},
   allSets = allSubsets[vertices];
   floodingSets = Select[allSets, isFloodingCascadeSet[#, adjacencyList, vertices] &];
   polynomial = Total[x^Length[#] & /@ floodingSets];
   {floodingSets, polynomial}
   ]

(* Example 2.12: 4-vertex cycle graph (square) *)
Print["=== Example 2.12: 4-vertex cycle graph ==="]

(* Define the 4-cycle graph (square) *)
verticesEx212 = {1, 2, 3, 4};
edgesEx212 = {{1, 2}, {2, 3}, {3, 4}, {4, 1}};

(* Create adjacency list *)
adjacencyListEx212[1] = {2, 4};
adjacencyListEx212[2] = {1, 3};
adjacencyListEx212[3] = {2, 4};
adjacencyListEx212[4] = {3, 1};

(* Compute flood polynomial *)
{floodingSetsEx212, polynomialEx212} = floodPolynomial[adjacencyListEx212, verticesEx212];

Print["Graph: 4-cycle (square) with vertices {1,2,3,4}"];
Print["Edges: ", edgesEx212];
Print["Flooding cascade sets: ", floodingSetsEx212];
Print["Number of flooding cascade sets by size:"];
Print["  Size 2: ", Length[Select[floodingSetsEx212, Length[#] == 2 &]]];
Print["  Size 3: ", Length[Select[floodingSetsEx212, Length[#] == 3 &]]];
Print["  Size 4: ", Length[Select[floodingSetsEx212, Length[#] == 4 &]]];
Print["Flood polynomial F_G(x) = ", polynomialEx212];
Print["Expected: x^4 + 4*x^3 + 2*x^2"];
Print["Match: ", polynomialEx212 == x^4 + 4*x^3 + 2*x^2];
Print[""]

(* Verify by substituting x=1 to get total number of flooding cascade sets *)
totalFloodingSetsEx212 = polynomialEx212 /. x -> 1;
Print["Total flooding cascade sets (x=1): ", totalFloodingSetsEx212];
Print["Actual count: ", Length[floodingSetsEx212]];
Print[""]

(* Example 3.3: Two graphs with same flood polynomial but different minimal flooding cascade sets *)
Print["=== Example 3.3: Graphs with same flood polynomial ==="]
Print["P_8 (path with 8 vertices) and P_4 ⊕ O_4 (path-4 joined with cycle-4)"]
Print["Both have flood polynomial: x^8 + 6*x^7 + 10*x^6 + 4*x^5"]
Print[""]

(* Define P_8 - path graph with 8 vertices *)
Print["--- Graph 1: P_8 (Path with 8 vertices) ---"]
verticesP8 = Range[8];
edgesP8 = Table[{i, i + 1}, {i, 1, 7}];

(* Create adjacency list for P_8 *)
adjacencyListP8[1] = {2};
adjacencyListP8[8] = {7};
Do[adjacencyListP8[i] = {i - 1, i + 1}, {i, 2, 7}];

Print["Vertices: ", verticesP8];
Print["Edges: ", edgesP8];

(* Compute flood polynomial for P_8 *)
{floodingSetsP8, polynomialP8} = floodPolynomial[adjacencyListP8, verticesP8];

Print["Flood polynomial F_P8(x) = ", polynomialP8];
Print["Total flooding cascade sets: ", Length[floodingSetsP8]];

(* Find minimal flooding cascade sets for P_8 *)
minimalFloodingP8 = Select[floodingSetsP8,
  Function[set,
   AllTrue[Subsets[set],
    Function[subset,
     subset == set || !isFloodingCascadeSet[subset, adjacencyListP8, verticesP8]]]]];

Print["Minimal flooding cascade sets for P_8: ", minimalFloodingP8];
Print["Number of minimal flooding cascade sets: ", Length[minimalFloodingP8]];
Print[""]

(* Define P_4 ⊕ O_4 - path with 4 vertices joined with 4-cycle *)
Print["--- Graph 2: P_4 ⊕ O_4 (Path-4 joined with Cycle-4) ---"]
verticesP4O4 = Range[8];
(* Path part: vertices 1-2-3-4, Cycle part: vertices 5-6-7-8 connected in a cycle *)
edgesP4O4 = {{1, 2}, {2, 3}, {3, 4}, {5, 6}, {6, 7}, {7, 8}, {8, 5}};

(* Create adjacency list for P_4 ⊕ O_4 *)
adjacencyListP4O4[1] = {2};
adjacencyListP4O4[2] = {1, 3};
adjacencyListP4O4[3] = {2, 4};
adjacencyListP4O4[4] = {3};
adjacencyListP4O4[5] = {6, 8};
adjacencyListP4O4[6] = {5, 7};
adjacencyListP4O4[7] = {6, 8};
adjacencyListP4O4[8] = {7, 5};

Print["Vertices: ", verticesP4O4];
Print["Edges: ", edgesP4O4];
Print["Structure: Path {1-2-3-4} ⊕ Cycle {5-6-7-8}"];

(* Compute flood polynomial for P_4 ⊕ O_4 *)
{floodingSetsP4O4, polynomialP4O4} = floodPolynomial[adjacencyListP4O4, verticesP4O4];

Print["Flood polynomial F_P4⊕O4(x) = ", polynomialP4O4];
Print["Total flooding cascade sets: ", Length[floodingSetsP4O4]];

(* Find minimal flooding cascade sets for P_4 ⊕ O_4 *)
minimalFloodingP4O4 = Select[floodingSetsP4O4,
  Function[set,
   AllTrue[Subsets[set],
    Function[subset,
     subset == set || !isFloodingCascadeSet[subset, adjacencyListP4O4, verticesP4O4]]]]];

Print["Minimal flooding cascade sets for P_4 ⊕ O_4: ", minimalFloodingP4O4];
Print["Number of minimal flooding cascade sets: ", Length[minimalFloodingP4O4]];
Print[""]

(* Compare the results *)
Print["--- Comparison ---"];
Print["Expected flood polynomial: x^8 + 6*x^7 + 10*x^6 + 4*x^5"];
Print["P_8 polynomial matches: ", polynomialP8 == x^8 + 6*x^7 + 10*x^6 + 4*x^5];
Print["P_4⊕O_4 polynomial matches: ", polynomialP4O4 == x^8 + 6*x^7 + 10*x^6 + 4*x^5];
Print["Same flood polynomials: ", polynomialP8 == polynomialP4O4];
Print["Number of minimal flooding sets  (P8): ", Length[minimalFloodingP8] , "   number of minimal flooding sets  (P_4 ⊕ O_4):" , Length[minimalFloodingP4O4]];
Print[""]

(* Example 3.17: Free vertices example *)
Print["=== Example 3.17: Graphs with same flood polynomial but different free vertices ==="]
Print["P_6 (path with 6 vertices) and P_3 ⊕ C_3 (path-3 joined with cycle-3)"]
Print["Both have flood polynomial: x^4(x+1)(x+3) = x^6 + 4*x^5 + 3*x^4"]
Print[""]

(* Function to check if a vertex is free *)
(* A vertex v is free if for every flooding cascade set C containing v, C-{v} is also flooding *)
isFreeVertex[vertex_, adjacencyList_, vertices_] :=
  Module[{floodingSetsWithVertex, floodingSetsWithoutVertex},
   {floodingSetsWithVertex, _} = floodPolynomial[adjacencyList, vertices];
   floodingSetsWithVertex = Select[floodingSetsWithVertex, MemberQ[#, vertex] &];
   AllTrue[floodingSetsWithVertex,
    Function[set,
     isFloodingCascadeSet[Complement[set, {vertex}], adjacencyList, vertices]]]
   ]

(* Define P_6 - path graph with 6 vertices *)
Print["--- Graph 1: P_6 (Path with 6 vertices) ---"]
verticesP6 = Range[6];
edgesP6 = Table[{i, i + 1}, {i, 1, 5}];

(* Create adjacency list for P_6 *)
adjacencyListP6[1] = {2};
adjacencyListP6[6] = {5};
Do[adjacencyListP6[i] = {i - 1, i + 1}, {i, 2, 5}];

Print["Vertices: ", verticesP6];
Print["Edges: ", edgesP6];

(* Compute flood polynomial for P_6 *)
{floodingSetsP6, polynomialP6} = floodPolynomial[adjacencyListP6, verticesP6];

Print["Flood polynomial F_P6(x) = ", polynomialP6];
Print["Factored form: x^4(x+1)(x+3) = ", Expand[x^4*(x + 1)*(x + 3)]];
Print["P_6 matches expected: ", polynomialP6 == Expand[x^4*(x + 1)*(x + 3)]];

(* Find free vertices in P_6 *)
freeVerticesP6 = Select[verticesP6, isFreeVertex[#, adjacencyListP6, verticesP6] &];
Print["Free vertices in P_6: ", freeVerticesP6];
Print["Number of free vertices in P_6: ", Length[freeVerticesP6]];
Print[""]

(* Define P_3 ⊕ C_3 - path with 3 vertices joined with 3-cycle *)
Print["--- Graph 2: P_3 ⊕ C_3 (Path-3 joined with Cycle-3) ---"]
verticesP3C3 = Range[6];
(* Path part: vertices 1-2-3, Cycle part: vertices 4-5-6 connected in a cycle *)
edgesP3C3 = {{1, 2}, {2, 3}, {4, 5}, {5, 6}, {6, 4}};

(* Create adjacency list for P_3 ⊕ C_3 *)
adjacencyListP3C3[1] = {2};
adjacencyListP3C3[2] = {1, 3};  (* vertex 2 is the free vertex *)
adjacencyListP3C3[3] = {2};
adjacencyListP3C3[4] = {5, 6};
adjacencyListP3C3[5] = {4, 6};
adjacencyListP3C3[6] = {4, 5};

Print["Vertices: ", verticesP3C3];
Print["Edges: ", edgesP3C3];
Print["Structure: Path {1-2-3} ⊕ Cycle {4-5-6}"];

(* Compute flood polynomial for P_3 ⊕ C_3 *)
{floodingSetsP3C3, polynomialP3C3} = floodPolynomial[adjacencyListP3C3, verticesP3C3];

Print["Flood polynomial F_P3⊕C3(x) = ", polynomialP3C3];
Print["P_3⊕C_3 matches expected: ", polynomialP3C3 == Expand[x^4*(x + 1)*(x + 3)]];

(* Find free vertices in P_3 ⊕ C_3 *)
freeVerticesP3C3 = Select[verticesP3C3, isFreeVertex[#, adjacencyListP3C3, verticesP3C3] &];
Print["Free vertices in P_3⊕C_3: ", freeVerticesP3C3];
Print["Number of free vertices in P_3⊕C_3: ", Length[freeVerticesP3C3]];
Print[""]

(* Compare results *)
Print["--- Comparison ---"];
Print["Expected flood polynomial: x^4(x+1)(x+3) = ", Expand[x^4*(x + 1)*(x + 3)]];
Print["P_6 polynomial matches: ", polynomialP6 == Expand[x^4*(x + 1)*(x + 3)]];
Print["P_3⊕C_3 polynomial matches: ", polynomialP3C3 == Expand[x^4*(x + 1)*(x + 3)]];
Print["Same flood polynomials: ", polynomialP6 == polynomialP3C3];
Print["Number of free vertices (P_6): ", Length[freeVerticesP6]];
Print["Number of free vertices (P_3⊕C_3): ", Length[freeVerticesP3C3]];
Print["Same number of free vertices: ", Length[freeVerticesP6] == Length[freeVerticesP3C3]];
Print[""]

Print["Key insight: The factor (x+1) in the flood polynomial gives an upper bound"];
Print["for the number of free vertices, but doesn't determine the exact count."];
Print[""]

(* Summary *)
Print["=== Summary ==="];
Print["Definition 2.10 established that the flood polynomial counts flooding cascade sets"];
Print["Example 2.12 showed a 4-cycle has F_G(x) = x^4 + 4*x^3 + 2*x^2"];
Print["Example 3.3 demonstrated two different graphs (P_8 and P_4⊕O_4) with the same flood polynomial"];
Print["  but different numbers of minimal flooding cascade sets"];
Print["Example 3.17 showed two different graphs (P_6 and P_3⊕C_3) with the same flood polynomial"];
Print["  but different numbers of free vertices"];
Print["These examples demonstrate that flood polynomials don't uniquely determine:"];
Print["  - Graph structure"];
Print["  - Number of minimal flooding cascade sets"];
Print["  - Number of free vertices"];
Print[""]
Print["Computation completed successfully!"];

Looking for a review in terms of approach, clarity, performance, etc. Any help would be greatly appreciated.

\$\endgroup\$

0

Reset to default

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.