Closed symmetric monoidal structures on the category of graphs (Q6575457)

Several products such as the box product (also called cartesian product), the Kronecker product, the lexicographic product and the strong product among others are considered in graph theory [\textit{W. Imrich} and \textit{S. Klavžar}, Product graphs. Structure and recognition. With a foreword by Peter Winkler. Chichester: Wiley (2000; Zbl 0963.05002)]. This paper considers which graph products define a closed symmetricc monoidal structure on the category of graphs. Monoidal structures are a natural framework for capturing abstract products on a given category.\N\NDiscrete homotopy theory, an area of mathematics concerned with applying techniques from homotopy theory to study combinatorial properties of graphs, are now under active development, as can be seen in the A-homotopy theory [\textit{E. Babson} et al., J. Algebr. Comb. 24, No. 1, 31--44 (2006; Zbl 1108.05030); \textit{H. Barcelo} and \textit{R. Laubenbacher}, Discrete Math. 298, No. 1--3, 39--61 (2005; Zbl 1082.37050); \textit{D. Carranza} and \textit{C. Kapulkin}, ``Cubical setting for discrete homotopy theory, revisited'', Preprint, \url{arXiv:2202.03516}] and the \(\times\)-homotopy theory [\textit{A. Dochtermann}, Eur. J. Comb. 30, No. 2, 490--509 (2009; Zbl 1167.05017); \textit{A. Dochtermann}, Electron. Notes Discrete Math. 31, 131--136 (2008; Zbl 1267.05081); \textit{T. Chih} and \textit{L. Scull}, J. Algebr. Comb. 53, No. 4, 1231--1251 (2021; Zbl 1467.05175)] among others. Different products of discrete homotopy theory use different graph products, ending up in similar results with similar looking proofs. This paper is a first step towards a synthetic theory of the desired properties of the product.\N\NThe main result in the paper is the following (Theorem 4.11).\N\NTheorem. The category of (reflective) graphs carries precisely two closed symmetric monoidal structures, namely, the box product and the categorical product.