Factors of disconnected graphs and polynomials with nonnegative integer coefficients

Authors

  • Christiaan E. van de Woestijne Montanuniversit√§t Leoben, Austria

DOI:

https://doi.org/10.26493/1855-3974.202.37f

Keywords:

graphs, monoids, factorisation

Abstract

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

Published

2012-04-03

Issue

Section

Articles