The k-distance Graph Operator

Students: David Lund, Gregory Demo

Faculty Mentor: Dr. Oleksiy Al-saadi

Computer Science

College of Science, Technology, and Business

After seeing interesting patterns within cellular automata like Conway’s Game of Life, we chose to investigate patterns of the k-distance operator in graph theory. Our main focus is on periodicity. We generated transition diagrams which show us which graphs lead to other graphs after an application of the k-distance operator. Periodicity can be identified in any cycle of this graph. We proved the k-distance operator is omni-weak periodic by presenting an infinite graph class which describes a graph with any sized period for any value of k. We identify an upper bound for the maximum clique size of 2-distance graphs and present an infinite graph class that shows strength. We identify a sufficient condition for a graph to have a graph with one connected component resulting from the 2-distance operator.