Generalized stepwise transmission irregular graphs

Abstract

The transmission TrG(u) of a vertex u of a connected graph G is the sum
of distances from u to all other vertices. G is a stepwise transmission irregular
(STI) graph if |TrG(u) − TrG(v)| = 1 holds for any edge uv ∈ E(G). In this
paper, generalized STI graphs are introduced as the graphs G such that for
some k ≥ 1 we have |TrG(u) − TrG(v)| = k for any edge uv of G. It is proved
that generalized STI graphs are bipartite and that as soon as the minimum
degree is at least 2, they are 2-edge connected. Among the trees, the only
generalized STI graphs are stars. The diameter of STI graphs is bounded and
extremal cases discussed. The Cartesian product operation is used to obtain
highly connected generalized STI graphs. Several families of generalized STI
graphs are constructed.