Bound on the Exponents of a Class of Two-Colored Digraphs

Abstract

A two-colored digraph \(D\) is primitive if there exist nonnegative integers \(h\) and \(k\) with \(h+k > 0\) such that for each pair \((i,j)\) of vertices there exists an \((h, k)\)-walk in \(D\) from \(i\) to \(j\). The exponent of the primitive two-colored digraph \(D\) is the minimum value of \(h + k\) taken over all such \(h\) and \(k\). In this paper, we consider the exponents of families of two-colored digraphs of order \(n\) obtained by coloring the digraph that has the exponent \((n – 1)^2\). We give the tight upper bound on the exponents, and the characterization of the extremal two-colored digraph.