A strong edge coloring of a simple graph G = (V,E) is an assignment of colors to the edges such that no two edges at distance at most two in G receive the same color. The Wiener index of G is the sum of shortest path lengths between every pair of distinct vertices in G. Andersen proved that the strong chromatic index of cubic graphs is at most 10. In this study, we propose a better approximation method based on a tabu search algorithm applied to fullerene graphs, an important subclass of cubic graphs with degree 3. In addition, we present an exact algorithm for calculating the Wiener index that exploits the symmetries of the graph to reduce computational complexity. Both algorithms have been implemented and tested on fullerene graphs Cn for 70 ≤ n ≤ 100 demonstrating their effectiveness and applicability

Keywords