Modeling and Analysis of Small Cage Graphs: A New Algorithmic Approach

Abstract

A cage graph is a specific type of graph where all its nodes have the same regularity and the same girth. There is a limited amount of instances of cage graphs because they must meet specific boundaries regarding the number of nodes. In this paper, a study about the smallest instances of cage graphs is proposed, where an algorithm is presented so as to model the behavior of each instance when it comes to move from one given source node towards a particular destination node. In order to facilitate the design of those algorithms, a node distribution scheme is exhibited to identify the nodes involved in each case, as well as a port identification scheme so as to label the edges attached to each node. In summary, the objective of the study is find the shortest path to move among any pair of nodes within the smallest cage graphs by means of designing an efficient algorithm for each particular case, where such algorithms meet the requirements with a limited number of steps.