Graph theory, a relatively young part of combinatorics, has seen a recent increase in investigation as applications in other fields and analogs in other domains of math are discovered and expanded. Projects such as Hoppe and Petrone’s Encyclopedia of Finite Graphs have gone to great lengths to increase the accessibility of knowledge about special properties of graphs known as graph invariants. Invariants include characteristics such as the number of vertices of a graph, the number of connected components of a graph, and the ability of the graph to be embedded in a plane or other surface. Another such invariant is the graph’s factorization into Cartesian-prime factors. A graph’s factorization, somewhat like that of a number’s factorization, is a representation of the graph as a minimal product of nontrivial components. Evidence of these components is repeated throughout the graph’s structure. This invariant can be modeled through a visual representation or by sets of numbers describing the vertices and edges of a graph. I use the latter method and an algorithm in Python to calculate the prime factorization of graphs of n<(TBD) for finite connected graphs.

A Survey of Graph Invariants: Cartesian-Prime Factorization