×

Unique prime Cartesian factorization of graphs over finite fields. (English) Zbl 1191.05092

Summary: A fundamental result, due to G. Sabidussi [Math. Z. 72, 446–457 (1960; Zbl 0093.37603)] and V. G. Vizing [Vychisl. Sistemy, Novosibirsk 9, 30–43 (1963; Zbl 0194.25203)] states that every connected graph has a unique prime factorization relative to the Cartesian product; but disconnected graphs are not uniquely prime factorable. This paper describes a system of modular arithmetic on graphs under which both connected and disconnected graphs have unique prime Cartesian factorizations.

MSC:

05C99 Graph theory
05C76 Graph operations (line graphs, products, etc.)