On Transmission Irregular Cubic Graphs of an Arbitrary Order

Abstract

The transmission of a vertex v of a graph G is the sum of distances from v to all the other vertices of G. A transmission irregular graph (TI graph) has mutually distinct vertex transmissions. In 2018, Alizadeh and Klavžar posed the following question: do there exist infinite families of regular TI graphs? An infinite family of TI cubic graphs of order 118+72k, k≥0, was constructed by Dobrynin in 2019. In this paper, we study the problem of finding TI cubic graphs for an arbitrary number of vertices. It is shown that there exists a TI cubic graph of an arbitrary even order n≥22. Almost all constructed graphs are contained in twelve infinite families.

Keywords

• cubic graph
• graph invariant
• vertex transmission
• transmission irregular graph
• Wiener complexity