On arc connectivity of direct-product digraphs. (English) Zbl 1258.05042

Summary: Four natural orientations of the direct product of two digraphs are introduced in this paper. Sufficient and necessary conditions for these orientations to be strongly connected are presented, as well as an explicit expression of the arc connectivity of a class of direct-product digraphs.


05C20 Directed graphs (digraphs), tournaments
05C40 Connectivity
05C76 Graph operations (line graphs, products, etc.)
Full Text: DOI


[1] W. Imrich and S. Klav\vzar, Product Graph, Structure and Recognition, Wiley-Interscience, New York, NY, USA, 2000. · Zbl 1038.20043
[2] Y. Chao, Connectivity and fault-diameter of product graph [Ph.D. thesis], University of Science and Technology of China, 2007.
[3] P. M. Weichsel, “The Kronecker product of graphs,” Proceedings of the American Mathematical Society, vol. 13, pp. 47-52, 1962. · Zbl 0102.38801
[4] R. Guji and E. Vumar, “A note on the connectivity of Kronecker products of graphs,” Applied Mathematics Letters, vol. 22, no. 9, pp. 1360-1363, 2009. · Zbl 1173.05331
[5] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, Macmillan Press, London, UK, 1976. · Zbl 1226.05083
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.