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 |
| _version_ | 1828781779149914112 |
|---|---|
| author | Olga O'Mahony Rachel Quinlan |
| author_facet | Olga O'Mahony Rachel Quinlan |
| author_sort | Olga O'Mahony |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-11T17:39:24Z |
| format | Article |
| id | doaj.art-5f9f5289b6e44181a0866c78b762fdc0 |
| institution | Directory Open Access Journal |
| issn | 2338-2287 |
| language | English |
| last_indexed | 2024-12-11T17:39:24Z |
| publishDate | 2019-10-01 |
| publisher | Indonesian Combinatorial Society (InaCombS); Graph Theory and Applications (GTA) Research Centre; University of Newcastle, Australia; Institut Teknologi Bandung (ITB), Indonesia |
| record_format | Article |
| series | Electronic Journal of Graph Theory and Applications |
| spelling | doaj.art-5f9f5289b6e44181a0866c78b762fdc02022-12-22T00:56:35ZengIndonesian Combinatorial Society (InaCombS); Graph Theory and Applications (GTA) Research Centre; University of Newcastle, Australia; Institut Teknologi Bandung (ITB), IndonesiaElectronic Journal of Graph Theory and Applications2338-22872019-10-017232934710.5614/ejgta.2019.7.2.10156Exponent-critical primitive graphs and the Kronecker productOlga O'Mahony0Rachel Quinlan1National University of Ireland, Galway, IrelandNational University of Ireland, Galway, IrelandA 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.https://www.ejgta.org/index.php/ejgta/article/view/623primitive graph, exponent, graph kronecker product |
| spellingShingle | Olga O'Mahony Rachel Quinlan Exponent-critical primitive graphs and the Kronecker product Electronic Journal of Graph Theory and Applications primitive graph, exponent, graph kronecker product |
| title | Exponent-critical primitive graphs and the Kronecker product |
| title_full | Exponent-critical primitive graphs and the Kronecker product |
| title_fullStr | Exponent-critical primitive graphs and the Kronecker product |
| title_full_unstemmed | Exponent-critical primitive graphs and the Kronecker product |
| title_short | Exponent-critical primitive graphs and the Kronecker product |
| title_sort | exponent critical primitive graphs and the kronecker product |
| topic | primitive graph, exponent, graph kronecker product |
| url | https://www.ejgta.org/index.php/ejgta/article/view/623 |
| work_keys_str_mv | AT olgaomahony exponentcriticalprimitivegraphsandthekroneckerproduct AT rachelquinlan exponentcriticalprimitivegraphsandthekroneckerproduct |