The Transitivity of special Graph Classes

Abstract

Let $G=(V,E)$ be a graph. The transitivity of a graph $G$, denoted $Tr(G)$, equals the maximum order $k$ of a partition $\pi =\{V_1,V_2,\dots ,V_k\}$ of $V$ such that for r=every $i,j,1\le i<j\le k,V_i$ dominates $V_j$. We consider the transitivity in many special classes of graphs, including cactus graphs, coronas, Cartesian products, and joins. We also consider the effects of vertex or edge deletion and edge addition on the transivity of a graph.

We dedicate this paper to the memory of professor Bohdan Zelinka for his pioneering work on domative of graphs.