Abstract
The usage of hypercubes as network architectures motivates the task of finding sparse spanners of hypercubes with good properties. These include maintaining the distance between vertices or reducing the maximal degree of the spanner.
Namely, a 3-spanner guarantees that neighbours in the original graph remain within distance 3 in the spanner. A genetic algorithm designed for finding a 3-spanner of minimal size is extended by adding two new mutations.
Further, a fitness function that aims for reduction of the maximal degree in the spanner while keeping the 3-spanner property is proposed. This fitness function brings intriguing results that combine both the mentioned properties, improve currently known size of 3-spanner with the minimal maximal degree and give a promising perspective for further improvements.