Exponent-critical primitive graphs and the Kronecker product
A directed graph is primitive of exponent <em>t</em> if it contains walks of length <em>t</em> between all pairs of vertices, and <em>t</em> is minimal with this property. Moreover, it is exponent-critical if the deletion of any arc results in an imprimitive graph...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Indonesian Combinatorial Society (InaCombS); Graph Theory and Applications (GTA) Research Centre; University of Newcastle, Australia; Institut Teknologi Bandung (ITB), Indonesia
2019-10-01
|
| Series: | Electronic Journal of Graph Theory and Applications |
| Subjects: | |
| Online Access: | https://www.ejgta.org/index.php/ejgta/article/view/623 |
| Summary: | A directed graph is primitive of exponent <em>t</em> if it contains walks of length <em>t</em> between all pairs of vertices, and <em>t</em> 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. |
|---|---|
| ISSN: | 2338-2287 |