Exponent-critical primitive graphs and the Kronecker product

Rachel Quinlan

doi:10.5614/ejgta.2019.7.2.10

Exponent-critical primitive graphs and the Kronecker product

Rachel Quinlan

Mathematics

University of Galway

Research output: Contribution to a Journal (Peer & Non Peer) › Article › peer-review

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.

Original language	English (Ireland)
Pages (from-to)	329-347
Number of pages	19
Journal	Electronic Journal Of Graph Theory And Applications
Volume	7
Issue number	2
DOIs	https://doi.org/10.5614/ejgta.2019.7.2.10
Publication status	Published - 1 Jan 2019

Keywords

Exponent
Graph Kronecker product Mathematics Subject Classification
Primitive graph

Authors (Note for portal: view the doc link for the full list of authors)

Authors
O'Mahony, O,Quinlan, R

Access to Document

10.5614/ejgta.2019.7.2.10

Cite this

@article{99a08d295ea544cbb2c908d5f1014031,

title = "Exponent-critical primitive graphs and the Kronecker product",

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 = "Exponent, Graph Kronecker product Mathematics Subject Classification, Primitive graph",

author = "Rachel Quinlan",

note = "Publisher Copyright: {\textcopyright} 2019, Indonesian Combinatorics Society.",

year = "2019",

month = jan,

day = "1",

doi = "10.5614/ejgta.2019.7.2.10",

language = "English (Ireland)",

volume = "7",

pages = "329--347",

journal = "Electronic Journal Of Graph Theory And Applications",

number = "2",

}

TY - JOUR

T1 - Exponent-critical primitive graphs and the Kronecker product

AU - Quinlan, Rachel

PY - 2019/1/1

Y1 - 2019/1/1

N2 - 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.

AB - 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.

KW - Exponent

KW - Graph Kronecker product Mathematics Subject Classification

KW - Primitive graph

UR - https://www.scopus.com/pages/publications/85074698262

U2 - 10.5614/ejgta.2019.7.2.10

DO - 10.5614/ejgta.2019.7.2.10

M3 - Article

VL - 7

SP - 329

EP - 347

JO - Electronic Journal Of Graph Theory And Applications

JF - Electronic Journal Of Graph Theory And Applications

IS - 2

ER -

Exponent-critical primitive graphs and the Kronecker product

Abstract

Keywords

Authors (Note for portal: view the doc link for the full list of authors)

Access to Document

Other files and links

Fingerprint

Cite this