Exponent-critical primitive graphs and the Kronecker product

Olga O'Mahony (National University of Ireland, Galway, Ireland)
Rachel Quinlan (National University of Ireland, Galway, Ireland)

Electronic Journal of Graph Theory and Applications (EJGTA)
Vol 7, No 2 (2019): Electronic Journal of Graph Theory and Applications

A directed graph is primitive of exponent t if it contains walks of length t between all pairs of vertices, and t is minimal with this property. Moreover, it is exponent-critical if the deletion of any arc results in an imprimitive graph or in a primitive graph with strictly greater exponent. We establish necessary and sufficient conditions for the Kronecker product of a pair of graphs to be exponent-critical of prescribed exponent, defining some refinements of the concept of exponent-criticality in the process.