Mathematical Research Seminar

 

According to the standard definition, a distance magic labeling of a graph of order n is a bijective labeling of its vertices with integers from 1 to n such that each vertex has the same sum of the labels of its neighbors. A graph is said to be distance magic if it admits a distance magic labeling.

Our focus is on tetravalent graphs. In this case, we are equipped with a useful observation due to Miklavič and Šparl that links the property of a regular graph being distance magic to the eigenvalues and eigenvectors of its adjacency matrix. Moreover, this observation provides an alternative definition of a distance magic labeling, which is often more convenient to work with. We will discuss this observation and illustrate it with some examples. We will also present data obtained via computer analysis, showing that tetravalent distance magic graphs of small order are extremely rare. In fact, out of nearly nine million connected tetravalent graphs up to order 16, only nine are distance magic. Finally, we will show how to construct larger tetravalent distance magic graphs from smaller ones, thereby determining the orders for which a connected tetravalent distance magic graph exists.

This is joint work with Primož Šparl.