Exponent-critical primitive graphs and the Kronecker product

Olga O'Mahony, Rachel Quinlan

Abstract


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.

Keywords


primitive graph, exponent, graph Kronecker product

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2019.7.2.10

Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats