Complete Multipartite Graphs are Pansophical

Abstract

Given a graph \( G \), we are interested in finding disjoint paths for a given set of distinct pairs of vertices. In 2017, we formally defined a new parameter, the pansophy of \( G \), in the context of the disjoint path problem.

In this paper, we construct a method to determine the pansophy of any complete bipartite graph, and then generalize the method to compute the pansophy of any complete multipartite graph. We close with future research directions.

Keywords: Pansophy, interconnection networks, graphs, algorithms, vertex disjoint paths