There were two causes of failure for an incorrect approximation in the program. Primarily, although rarely, error was caused by the upper bound for checking random partitions because the algorithm terminated before a partition with the correct number was found. Since there is no proper way to measure accuracy, precision was looked at instead. This means that an error occurs when the approximation algorithm returns different results for the same graph. At the same time, we minimized error by approximating twice and selecting the larger result. Therefore, the algorithm decreased the chances that a larger size number was missed.
It is not too surprising that the transitivity number is on average 2.4 points larger than the domatic number because each set in a domatic partition must dominate the entire graph, thus, more vertices are needed per color in order to dominate an entire graph. In the future, we hope to expand the algorithms by improving approximation and speed. The algorithm can be further improved through potential brute force or increased partition checks. For brute force, the program would go through every possible partition sequentially and increment the partition size once it found a random partition of a certain size. This would guarantee 100% accuracy; however, there are simply too many possible partitions to practically check graphs with a large number of vertices (>10). This means that a brute force method would not be able to calculate the transitivity numbers, domatic number, and Grundy number in a reasonable amount of time for large graphs, but it could work for smaller graphs. The algorithm used in this research was designed with speed and accuracy in mind. In the initial design choice, random partition checks were considered instead of brute force because random partitioning has a higher likelihood of hitting the correct partition with luck. Furthermore, the upper limit for random partitions can be improved and modified specifically for each algorithm. This is the highest source of error because the program terminates earlier than it should in cases of error. However, error varies, and the upper limit must be improved for each specific algorithm. In future analysis, the number of edges of a graph can be related to the three properties. This is a significant point of analysis because there may be some property of the graph that is affecting the distance between the Grundy number, domatic number, and transitivity number. |