The approximation algorithm worked by increasing the partition size or the number of colors, starting at 2, until it does not find a transitive, domatic, or Grundy partition of that size. The algorithm is an approximation instead of a fully accurate result because there is an experimentally-derived termination point. There are too many partitions to brute force, or look through every single one, in a large graph.
The upper limit on the number of random partitions generated was 10, 000 ∗ 2^Ps where Ps was the partition size currently being checked. Essentially, the program continued generating random partitions until it found a new highest one. This upper limit was chosen experimentally based on many trials and finding the balance between speed and accuracy. This approximation algorithm is an improvement of previous methods because the numbers can be quickly calculated for large graphs with over ten vertices instead of by hand. One of the purposes of building these algorithms is to run various statistics on the three properties that would be difficult to find without algorithms. A few of the natural mathematical questions that we answered included: the relationship between the Grundy number and transitivity number and the relationship between the transitivity number and the domatic number. We ran all three algorithms for approximation on random graphs. Random graphs and random coloring were generated.
Figure 5: Graph generated from the algorithm where Tr(G) ≤ 7 and Γr(G) ≤ 4. The number in black shows the vertex set of the Grundy coloring, and the number in gray shows the vertex set of the transitivity partition.
The algorithm generated the graph in Figure 5 where Tr(G) = 7 and a Γr(G) = 5. This was a unique graph that was found with the use of the algorithm. This was a rare case, essentially a demonstration of what an algorithmic approach to transitivity can find.
Most of the time only 3 out of 100 random graphs of vertex size ten incorrectly approx- imated the transitivity or Grundy number. When we did this, 97 of them did not improve when we ran the approximation algorithm twice for the same graph and same property. In one case, the Grundy number was greater than the transitivity number. Therefore, from these results, we are confident that the program can approximate the domatic number, transitivity number, and Grundy number. Secondly, we were able successfully return a Grundy coloring, domatic partition, and transitivity partition of either a given graph or random graph. These algorithms are very good at finding these three partitions. This is a novel method for determining the domatic number, transitivity number, and Grundy number of graphs with less than 20 vertices quickly. After 20 vertices, the algorithm takes a more significant amount of time. Likewise, this is the first set of algorithms of its kind to generate domatic partitions, transitivity partitions, and Grundy colorings of any graph. We are confident that there is no Grundy partition of size six because we re-ran the algorithm on this specific graph with an increased upper limit of 6,400,000. Without this algorithm, it would not have been reasonably possible to find this partition. Class Structure
|