Factors of disconnected graphs and polynomials with nonnegative integer coefficients
Keywords:graphs, monoids, factorisation
AbstractWe investigate the uniqueness of factorisation of possibly disconnected finite graphs with respect to the Cartesian, the strong and the direct product. It is proved that if a graph has n connected components, where n is prime, or n = 1, 4, 8, 9, and satisfies some additional natural conditions, it factors uniquely under the given products. If, on the contrary, n = 6 or 10, all cases of nonunique factorisation are described precisely.
Articles in this journal are published under Creative Commons Attribution 4.0 International License