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

References

R.A. Brualdi and J.A. Ross, On the exponent of a primitive, nearly reducible matrix, Math. Oper. Res., 5(2):229--241, 1980.

F.R.K. Chung, Graphs with small diameter after edge deletion, Discrete Appl. Math., 37/38:73--94, 1992.

P. Erdos, A. Renyi and V. T. Sos, On a problem of graph theory, Studia Sci. Math. Hungar., 1:215--235, 1966.

T.W. Haynes, M.A. Henning, L.C. van~der Merwe and A. Yeo, Progress on the Murty-Simon Conjecture on diameter-2 critical graphs: a survey, J. Comb. Optim., 30(3):579--595, 2015.

J.C. Holladay and R.S. Varga, On powers of non-negative matrices, Proc. Amer. Math. Soc., 9:631--634, 1958.

Byeong~Moon Kim, Byung~Chul Song, and Woonjae Hwang, Nonnegative primitive matrices with exponent 2, Linear Algebra Appl., 407:162--168, 2005.

Byeong~Moon Kim, Byung~Chul Song, and Woonjae Hwang, Primitive graphs with given exponents and minimum number of edges, Linear Algebra Appl., 420(2-3:648--662, 2007.

C.W.H. Lam and J.H. van Lint, Directed graphs with unique paths of fixed length, J. Combinatorial Theory Ser. B, 24(3):331--337, 1978.

Po-Shen Loh and Jie Ma, Diameter critical graphs, J. Combin. Theory Ser. B, 117:34--58, 2016.

M.H. McAndrew, On the product of directed graphs, Proc. Amer. Math. Soc., 14:600--606, 1963.

U.S.R. Murty, On critical graphs of diameter {$2$}, Math. Mag., 41:138--140, 1968.

O. O'Mahony, Edge-minimal graphs of exponent 2, PhD thesis, National University of Ireland, Galway, 2017.

O. O'Mahony and R. Quinlan, Edge-minimal graphs of exponent 2, Linear Algebra Appl., 542:66--83, 2018.

O. Ore, Diameters in graphs, J. Combinatorial Theory, 5:75--81, 1968.

Tian~Ming Wang and Ke~Quan Ding, On some solutions of {$A^k=J-I$}, J. Math. Res. Exposition, 7(4):665--667, 1987.

H. Wielandt, Unzerlegbare, nicht negative Matrizen, Math. Z., 52:642--648, 1950.

Yaokun Wu and Qiao Li, An approach to solving {$A^k=J-I$}, Linear Algebra Appl., 373:121--142, 2003, Special issue on the Combinatorial Matrix Theory Conference (Pohang, 2002).


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